Ультимативный гайд по структурам данных и алгоритмам на Python. Часть 6: графы — моделируем всё, что связано

Графы, их вершины и рёбра

Классификация графов

  (0) --10-- (1)
   | \      / |
   5  6    4  |  <-- Ребро(0,1) вес 10, Ребро(0,4) вес 5, ...
   |   \  /   |      (Цифры в скобках - вершины)
  (4) --8-- (2)
   \       /
    7     3
     \   /
      (3)

Как закодировать граф?

Матрица смежности (Adjacency Matrix)

num_vertices = 5
# Инициализация матрицы нулями
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]

edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]
for u, v in edges:
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1 # Симметрично для неориентированного

print("Матрица смежности:")
for row in adj_matrix:
    print(row)
# Пример вывода:
# [0, 1, 0, 0, 1]
# [1, 0, 1, 1, 1]
# [0, 1, 0, 1, 0]
# [0, 1, 1, 0, 1]
# [1, 1, 0, 1, 0]

# Проверка ребра (1, 4): O(1)
print(f"\nРебро (1, 4) существует? {'Да' if adj_matrix[1][4] == 1 else 'Нет'}")

Список смежности (Adjacency List)

from collections import defaultdict

# Используем defaultdict(list)
adj_list = defaultdict(list)

edges = [(0, 1), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (3, 4)]

# Заполняем список смежности
for u, v in edges:
    adj_list[u].append(v)
    adj_list[v].append(u) # Для неориентированного графа

print("Список смежности:")
# Выводим содержимое словаря
for vertex in sorted(adj_list.keys()): # Сортируем ключи для предсказуемого вывода
    print(f"Вершина {vertex}: {sorted(adj_list[vertex])}") # Сортируем соседей для наглядности
# Пример вывода:
# Вершина 0: [1, 4]
# Вершина 1: [0, 2, 3, 4]
# Вершина 2: [1, 3]
# Вершина 3: [1, 2, 4]
# Вершина 4: [0, 1, 3]

# Получение соседей вершины 1: O(1) в среднем для словаря
print(f"\nСоседи вершины 1: {adj_list[1]}")

# Проверка ребра (1, 4): O(k), где k - степень вершины 1
print(f"Ребро (1, 4) существует? {'Да' if 4 in adj_list[1] else 'Нет'}")

Какой способ выбрать? Матрица или список?

Вывод

В большинстве случаев для Python выбирайте список смежности. Матрицу смежности стоит рассматривать только при специфических требованиях к плотным графам или O(1) проверке рёбер.

Обходим графы: BFS и DFS

Обход в ширину (BFS)

from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list) # Список смежности

    def add_edge(self, u, v, is_directed=False):
        """Добавляет ребро между u и v."""
        self.graph[u].append(v)
        if not is_directed:
            self.graph[v].append(u) # Для неориентированного

    def bfs(self, start_node):
        """Выполняет BFS графа, начиная с start_node."""
        if start_node not in self.graph:
            print(f"Стартовая вершина {start_node} отсутствует.")
            return []

        visited = {start_node} # Используем set для O(1) проверки
        queue = deque([start_node])
        result_order = [] # Список для хранения порядка обхода

        while queue:
            current_node = queue.popleft()
            result_order.append(current_node) # Обрабатываем

            for neighbor in self.graph[current_node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        print(f"BFS от {start_node}: {result_order}")
        return result_order

# --- Создаем граф (ориентированный) ---
# 0 -> 1, 0 -> 2
# 1 -> 2
# 2 -> 0, 2 -> 3
# 3 -> 3
g_bfs = Graph()
g_bfs.add_edge(0, 1, is_directed=True)
g_bfs.add_edge(0, 2, is_directed=True)
g_bfs.add_edge(1, 2, is_directed=True)
g_bfs.add_edge(2, 0, is_directed=True) # Цикл!
g_bfs.add_edge(2, 3, is_directed=True)
g_bfs.add_edge(3, 3, is_directed=True) # Петля!

-
g_bfs.bfs(2)
# Ожидаемый вывод: BFS от 2: [2, 0, 3, 1]

Обход в глубину (DFS)

from collections import defaultdict

class Graph: # Используем тот же класс, что и для BFS
    def __init__(self):
        self.graph = defaultdict(list)
        self.dfs_result_order = [] # Для хранения результата обхода

    def add_edge(self, u, v, is_directed=False):
        self.graph[u].append(v)
        if not is_directed:
            self.graph[v].append(u)

    # Вспомогательная рекурсивная функция
    def _dfs_recursive(self, vertex, visited):
        visited.add(vertex)           # 1. Пометить
        self.dfs_result_order.append(vertex) # 2. Обработать

        # 3. Для каждого соседа
        for neighbor in self.graph[vertex]:
            # 4. Если не посещен
            if neighbor not in visited:
                # 5. Рекурсивный вызов
                self._dfs_recursive(neighbor, visited)

    def dfs(self, start_node):
        """Выполняет DFS графа, начиная с start_node."""
        if start_node not in self.graph:
            print(f"Стартовая вершина {start_node} отсутствует.")
            return []

        visited = set()
        self.dfs_result_order = [] # Очищаем результат перед новым обходом
        self._dfs_recursive(start_node, visited) # Запускаем рекурсию
        print(f"DFS от {start_node}: {self.dfs_result_order}")
        return self.dfs_result_order

g_dfs = Graph()
g_dfs.add_edge(0, 1, is_directed=True); g_dfs.add_edge(0, 2, is_directed=True)
g_dfs.add_edge(1, 2, is_directed=True)
g_dfs.add_edge(2, 0, is_directed=True) # Цикл 0-2-0
g_dfs.add_edge(2, 3, is_directed=True)
g_dfs.add_edge(3, 3, is_directed=True) # Петля

g_dfs.dfs(2)
# DFS от 2: [2, 0, 1, 3]
# (Порядок может отличаться от BFS, т.к. DFS уходит вглубь: 2 -> 0 -> 1, затем возвращается и идет 2 -> 3)

BFS vs. DFS: краткое Сравнение

Заключение: графы освоены🏆

Понимание внутреннего устройства, асимптотической сложности (Big O) и алгоритмов работы с ними — это не академическая прихоть, а фундамент для написания по-настоящему эффективного, масштабируемого и элегантного кода на Python.
Знание алгоритмов и структур данных позволяет вам не просто решать задачи, а решать их правильно.