Графы

Дерево — структура удобная, но частная: у каждого узла в точности один родитель, а между любыми двумя узлами проложен единственный путь. Реальные связи устроены так не всегда.

Города соединены дорогами, причём из каждого можно выехать несколькими маршрутами. Атомы в молекуле связаны в кольца, а узлы электрической цепи соединяются проводниками, образующими контуры. Компьютеры в сети связаны друг с другом множеством путей. Всё это описывается самой общей структурой — графом.

К графам сводится множество практических задач, на первый взгляд не имеющих к ним отношения.

Слайды к главе. Определения, способы хранения графа, обходы в глубину и в ширину, компоненты связности и перколяция изложены также в шестой части лекции «Хеши, деревья и графы» с демонстрациями в терминале; слайды лекции доступны на сайте книги и в PDF.

Определения

Граф \( G = (V, E) \) складывается из множества вершин \( V \) (англ. vertices) и множества рёбер \( E \) (англ. edges), каждое из которых соединяет пару вершин.

Основные разновидности:

  • Неориентированный граф имеет рёбра, не снабжённые направлением: если из \( u \) можно попасть в \( v \), то и обратно тоже (дороги с двусторонним движением).
  • Ориентированный граф (орграф, англ. directed graph) снабжает рёбра направлением, и ребро \( (u, v) \), проведённое в одну сторону, не означает существования ребра \( (v, u) \) (односторонние улицы, ссылки между веб-страницами, зависимости, связывающие задачи).
  • Взвешенный граф приписывает каждому ребру число: длину дороги, сопротивление проводника, пропускную способность канала, энергию связи.

Терминология:

  • смежными называются вершины, соединённые ребром;
  • степень вершины равна числу рёбер, инцидентных ей (в орграфе различают входящую и исходящую степени);
  • путь есть последовательность вершин, в которой соседние соединены рёбрами;
  • цикл представляет собой путь, начинающийся и заканчивающийся в одной вершине;
  • связный граф позволяет добраться из любой вершины до любой другой;
  • компонента связности составляет максимальную связную часть графа;
  • петля соединяет вершину с самой собой, а кратными рёбрами называются несколько рёбер, проведённых между одной парой вершин.

Дерево есть связный неориентированный граф, не содержащий циклов, у которого рёбер на одно меньше, чем вершин. Граф без циклов, но не обязательно связный, называется лесом.

Способы хранения графа

От способа хранения зависят объём памяти и сложность операций; основных вариантов два.

Матрица смежности

Квадратная таблица \( n \times n \), где на пересечении \( i \)-й строки и \( j \)-го столбца стоит единица (или вес ребра), если ребро, ведущее из \( i \) в \( j \), существует, и ноль в противном случае. У неориентированного графа матрица симметрична.

n = 5
matrix = [[0] * n for _ in range(n)]  # граф без рёбер

def add_edge_matrix(matrix, u, v, directed=False):
    """Добавляет ребро в матрицу смежности (вершины нумеруются с нуля)."""
    matrix[u][v] = 1
    if not directed:
        matrix[v][u] = 1

Проверка наличия ребра между \( u \) и \( v \) выполняется за \( O(1) \). Однако памяти требуется \( O(n^2) \) независимо от числа рёбер, а перебор всех соседей вершины требует \( O(n) \), поскольку приходится просмотреть всю строку, даже если сосед всего один.

Список смежности

Для каждой вершины хранится список соседей, связанных с ней ребром.

from collections import defaultdict

graph = defaultdict(list)

def add_edge_list(graph, u, v, directed=False):
    """Добавляет ребро в список смежности."""
    graph[u].append(v)
    if not directed:
        graph[v].append(u)

Памяти требуется \( O(n + m) \), где \( m \) — число рёбер, а перебор соседей занимает время, пропорциональное их количеству. Платой является проверка конкретного ребра за \( O(\deg u) \) вместо \( O(1) \).

Выбор между ними. Для плотного графа, где число рёбер сравнимо с \( n^2 \), применяется матрица, для разреженного, где рёбер порядка \( n \), — список. Реальные графы почти всегда разреженные: у человека в социальной сети сотни друзей, а не миллионы, у атома в молекуле единицы связей. По умолчанию выбирается список смежности.

ОперацияМатрица смежностиСписок смежности
Память\( O(n^2) \)\( O(n + m) \)
Проверить ребро \( (u,v) \)\( O(1) \)\( O(\deg u) \)
Перебрать соседей \( u \)\( O(n) \)\( O(\deg u) \)
Добавить ребро\( O(1) \)\( O(1) \)

Третий способ, список рёбер, представляет собой перечень пар вершин. Для обходов он неудобен, зато подходит алгоритмам, перебирающим рёбра целиком, наподобие алгоритма Краскала, и в таком виде граф обычно поступает на вход.

Обходы графа

Обходом называется систематическое посещение всех вершин, достижимых из стартовой. У графа, в отличие от дерева, есть циклы, поэтому появляется обязательный элемент, множество посещённых вершин. Без него обход зациклится.

Поиск в глубину (DFS)

Из текущей вершины обход уходит как можно дальше вглубь, а когда идти больше некуда, возвращается и пробует другое направление. Это тот же обход в глубину, что и на деревьях, только с проверкой на повторное посещение.

def dfs_recursive(graph, vertex, visited=None):
    """Рекурсивный обход в глубину. Возвращает вершины в порядке обхода."""
    if visited is None:
        visited = set()
    visited.add(vertex)
    order = [vertex]
    for neighbour in sorted(graph[vertex]):
        if neighbour not in visited:
            order.extend(dfs_recursive(graph, neighbour, visited))
    return order

Рекурсивная запись удобна для чтения, но опасна на практике. Глубина рекурсии в Python по умолчанию ограничена примерно 1000, и если путь обхода длиннее тысячи вершин, например на цепочке из ста тысяч вершин, программа завершится с RecursionError. Поэтому DFS реализуют итеративно, заменяя стек вызовов явным стеком:

def dfs_iterative(graph, start):
    """Итеративный обход в глубину через явный стек."""
    visited = set()
    order = []
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        # соседей кладём в обратном порядке, чтобы снимать по возрастанию
        for neighbour in sorted(graph[vertex], reverse=True):
            if neighbour not in visited:
                stack.append(neighbour)
    return order

Проверка if vertex in visited стоит после снятия со стека, а не только перед добавлением. Одна и та же вершина попадает в стек по нескольку раз от разных соседей, поэтому отсеивать её необходимо в момент обработки.

Поиск в ширину (BFS)

Сначала посещаются все соседи стартовой вершины, затем соседи соседей и так далее, по расходящимся кругам. От DFS отличие в двух местах: вместо стека используется очередь, а вершина помечается посещённой в момент постановки в очередь.

from collections import deque

def bfs(graph, start):
    """Обход в ширину. Возвращает вершины в порядке обхода."""
    visited = {start}
    order = []
    queue = deque([start])
    while queue:
        vertex = queue.popleft()          # берём из начала очереди
        order.append(vertex)
        for neighbour in sorted(graph[vertex]):
            if neighbour not in visited:
                visited.add(neighbour)    # помечаем сразу при добавлении
                queue.append(neighbour)
    return order

В BFS вершина помечается посещённой в момент добавления в очередь, иначе она успеет попасть туда несколько раз.

Оба обхода работают за \( O(n + m) \): каждая вершина обрабатывается один раз, а каждое ребро просматривается один раз в ориентированном графе и дважды в неориентированном. Вызов sorted внутри приведённого обхода добавляет \( O(m \log n) \) и присутствует там ради воспроизводимого вывода. В рабочем коде списки смежности сортируют один раз заранее, как в задачах в конце главы. Выбор между двумя обходами определяется задачей:

  • BFS посещает вершины в порядке возрастания расстояния, отсчитанного от старта, поэтому он находит кратчайшие пути в невзвешенном графе;
  • DFS естественно записывается через рекурсию и применяется для поиска циклов, топологической сортировки, компонент связности и анализа структуры графа.

Слайды к главе. Кратчайшие пути, топологическая сортировка и минимальное остовное дерево изложены также в седьмой части лекции «Хеши, деревья и графы»; слайды лекции доступны на сайте книги и в PDF.

Кратчайшие пути

В невзвешенном графе кратчайший путь находит BFS, попутно запоминая расстояние и предка каждой вершины.

def bfs_shortest_paths(graph, start):
    """Расстояния (в рёбрах) и предки на кратчайших путях от start."""
    dist = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if neighbour not in dist:
                dist[neighbour] = dist[vertex] + 1
                parent[neighbour] = vertex
                queue.append(neighbour)
    return dist, parent

Путь восстанавливается проходом от конечной вершины по ссылкам parent до старта и разворотом полученного списка.

Если рёбра взвешенные, BFS уже не подходит, так как путь, составленный из трёх коротких рёбер, может оказаться короче одного длинного. Здесь применяется алгоритм Дейкстры, являющийся жадным: поддерживаются текущие оценки расстояний, и на каждом шаге берётся ещё не обработанная вершина с наименьшей оценкой, уже не подлежащей улучшению, после чего предпринимается попытка улучшить оценки её соседей; эта операция называется релаксацией.

import heapq

def dijkstra(graph, start):
    """Кратчайшие расстояния во взвешенном графе с неотрицательными весами.

    graph — список смежности вида {вершина: [(сосед, вес), ...]}.
    """
    dist = {start: 0}
    heap = [(0, start)]           # приоритетная очередь (расстояние, вершина)
    while heap:
        d, vertex = heapq.heappop(heap)
        if d > dist.get(vertex, float("inf")):
            continue              # устаревшая запись, вершина уже обработана
        for neighbour, weight in graph[vertex]:
            new_dist = d + weight
            if new_dist < dist.get(neighbour, float("inf")):
                dist[neighbour] = new_dist
                heapq.heappush(heap, (new_dist, neighbour))
    return dist

Куча, рассмотренная в главе про деревья, обеспечивает сложность \( O(m \log n) \). Приведённая реализация не уменьшает ключ записи, уже лежащей в куче, а кладёт в кучу новую запись; устаревшая запись, расстояние в которой больше текущей оценки, при извлечении пропускается. Веса обязаны быть неотрицательными: иначе вершина, уже снятая с кучи, может получить лучшую оценку, и оценка сложности перестаёт выполняться; для графов с отрицательными рёбрами применяют алгоритм Беллмана — Форда, который требует \( O(nm) \) и обнаруживает циклы отрицательного веса.

Топологическая сортировка

Пусть ориентированный граф описывает зависимости: ребро \( u \to v \) означает «\( u \) должно быть выполнено раньше \( v \)». Компиляция модулей, порядок расчётных этапов в пайплайне, установка пакетов ставят одну и ту же задачу — выстроить вершины в линию так, чтобы все рёбра шли слева направо. Это и есть топологическая сортировка, возможная тогда и только тогда, когда в графе нет циклов, иначе зависимости противоречивы.

Простейший способ — DFS: вершина добавляется в результат после всех потомков, а список в конце разворачивается. Чтобы обнаружить цикл, вершины различают тремя цветами: не посещённая, находящаяся в обработке и обработанная. Вершина, встреченная повторно, пока она ещё в обработке, лежит на текущем пути обхода, и ребро в неё замыкает цикл.

def topological_sort(graph, vertices):
    """Топологическая сортировка; при цикле возбуждает ValueError."""
    WHITE, GRAY, BLACK = 0, 1, 2  # не посещена, в обработке, обработана
    color = {vertex: WHITE for vertex in vertices}
    order = []

    def visit(vertex):
        color[vertex] = GRAY
        for neighbour in graph[vertex]:
            if color[neighbour] == GRAY:      # вершина на текущем пути
                raise ValueError(f"цикл через вершину {neighbour}")
            if color[neighbour] == WHITE:
                visit(neighbour)
        color[vertex] = BLACK
        order.append(vertex)      # добавляем на выходе из вершины

    for vertex in vertices:
        if color[vertex] == WHITE:
            visit(vertex)
    return order[::-1]            # разворачиваем

На графе \( a \to b \to c \to a \) функция возбуждает ValueError: цикл через вершину a; без проверки цвета она вернула бы порядок ['a', 'b', 'c'], нарушающий ребро \( c \to a \), без какой-либо ошибки. Рекурсивная функция visit к тому же исчерпает предел рекурсии на цепочке длиннее тысячи вершин. Без рекурсии обходится алгоритм Кана: он подсчитывает для каждой вершины число входящих рёбер, ставит в очередь вершины без входящих рёбер и, снимая вершину, уменьшает счётчики её соседей; если в итоге упорядочены не все вершины, в графе есть цикл. Оба способа требуют \( O(n + m) \).

В стандартной библиотеке начиная с Python 3.9 есть класс graphlib.TopologicalSorter, который при цикле возбуждает исключение graphlib.CycleError. Он принимает словарь, сопоставляющий вершине её предшественников, то есть рёбра в нём записаны в обратную сторону по сравнению со списками смежности; переданные без разворота списки смежности дали бы обратный порядок без какой-либо ошибки.

from graphlib import TopologicalSorter, CycleError

deps = {"b": ["a"], "c": ["b"]}    # вершина -> её предшественники
print(list(TopologicalSorter(deps).static_order()))   # ['a', 'b', 'c']

deps["a"] = ["c"]                  # a зависит от c: цикл
try:
    list(TopologicalSorter(deps).static_order())
except CycleError as err:
    print("цикл:", err.args[1])    # цикл: ['b', 'c', 'a', 'b']

Минимальное остовное дерево

Остовным деревом (англ. spanning tree) связного графа называется подмножество рёбер, связывающее все вершины и не содержащее циклов, то есть дерево, натянутое на все \( n \) вершин и собранное из \( n-1 \) ребра. Минимальным остовным деревом (MST) называется то, у которого суммарный вес рёбер наименьший. Классическая постановка требует соединить все дома оптоволокном, затратив минимум кабеля.

Два классических алгоритма, оба жадные:

  • Алгоритм Прима наращивает дерево из одной вершины: на каждом шаге добавляется самое лёгкое ребро, ведущее из уже построенной части наружу. Удобно реализуется через кучу, сложность \( O(m \log n) \). По существу это алгоритм Дейкстры, только вместо расстояния от старта минимизируется вес одного ребра.
  • Алгоритм Краскала исходит от рёбер: сортирует их все по весу и добавляет по очереди те, которые не образуют цикл. Проверка на цикл выполняется структурой «система непересекающихся множеств» (DSU): с сокращением путей и объединением по рангу её операции выполняются амортизированно почти за \( O(1) \), и сложность определяется сортировкой рёбер, \( O(m \log m) \).

Если в алгоритме Прима заменить «минимальное ребро» на «максимальное», получится максимальное остовное дерево; эта задача рассматривается в конце главы.

Графы в физических задачах

  • Электрические цепи. Схема представляет собой граф из узлов и ветвей. Законы Кирхгофа записываются через матрицу инцидентности, а число независимых контурных уравнений равно \( m - n + 1 \), то есть количеству рёбер, не вошедших в остовное дерево: каждое такое ребро вместе с путём по остову замыкает свой независимый контур, хотя эти контуры не обязаны совпадать с ячейками схемы.
  • Модель Изинга и перколяция. Спины на решётке служат вершинами, а взаимодействия соседей рёбрами. Алгоритмы кластерного обновления (Свендсена — Ванга, Вольфа) сводятся к поиску компонент связности, а перколяция — вопрос о существовании компоненты, соединяющей края решётки; на квадратной решётке, узлы которой заняты независимо с вероятностью \( p \), такая компонента в пределе бесконечной решётки появляется при \( p > p_c \approx 0{,}5927 \).
  • Молекулы и структуры. Атомы и химические связи образуют граф, а поиск колец в молекуле сводится к поиску циклов. На этом же представлении работают графовые нейронные сети, предсказывающие свойства веществ.
  • Марковские цепи и графы состояний. Состояния системы становятся вершинами, а переходы, снабжённые вероятностями, взвешенными рёбрами орграфа.
  • Трассировка и планирование. Разводка кабелей на установке, маршрут манипулятора, план эксперимента сводятся к задачам о кратчайшем пути или об остовном дереве.

Для практических расчётов реализовывать алгоритмы вручную не обязательно: готовые собраны в библиотеке NetworkX.

import networkx as nx

# граф-решётка 4 x 4 — например, узлы двумерной модели Изинга
lattice = nx.grid_2d_graph(4, 4)

print(nx.number_connected_components(lattice))       # компоненты связности
print(nx.shortest_path(lattice, (0, 0), (3, 3)))     # кратчайший путь
mst = nx.minimum_spanning_tree(lattice)              # остовное дерево

Разбираться в устройстве алгоритмов всё равно необходимо: библиотека не подскажет, что поставленная задача сводится к поиску компонент связности.

Разбор задач

Задачи рекомендуется сначала решить самостоятельно; они собраны в тренажёре.

Во всех задачах вершины нумеруются с единицы, а граф подаётся на вход списком рёбер: в первой строке числа \( n \) и \( m \), задающие количество вершин и рёбер, далее \( m \) строк с парами вершин.

Задача 1. Построить список смежности

Условие. Дан ориентированный граф, заданный списком рёбер. Требуется построить его список смежности: для каждой вершины \( i \) вывести число исходящих рёбер, а затем номера вершин, в которые они ведут, в порядке возрастания.

Идея решения. Прямая реализация определения. Заведём список списков и пройдём по рёбрам, добавляя конец каждого ребра в список его начала. Сортировка выполняется один раз в конце.

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]        # вершины нумеруются с единицы

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)                    # граф ориентированный: только u -> v

for vertex in range(1, n + 1):
    neighbours = sorted(graph[vertex])
    print(len(neighbours), *neighbours)

Сложность. По времени \( O(n + m \log n) \), поскольку чтение рёбер стоит \( O(m) \), а сортировка списков смежности даёт в сумме \( \sum_i d_i \log d_i \le m \log n \). По памяти \( O(n + m) \).

Задача 2. Перевести список рёбер в матрицу смежности

Условие. Дан ориентированный граф, заданный списком рёбер. Требуется вывести его матрицу смежности \( n \times n \): на пересечении \( i \)-й строки и \( j \)-го столбца стоит единица, если существует ребро, ведущее из \( i \) в \( j \).

Идея решения. Заведём нулевую матрицу и расставим единицы. Единственная тонкость заключается в том, что матрицу нельзя создавать через [[0] * n] * n. В этом случае получится \( n \) ссылок на один и тот же список, и запись в одну строку изменит все разом; устройство этой ловушки рассмотрено в главе про объекты и память.

n, m = map(int, input().split())
matrix = [[0] * n for _ in range(n)]      # именно так, а не [[0] * n] * n

for _ in range(m):
    u, v = map(int, input().split())
    matrix[u - 1][v - 1] = 1              # переходим к нумерации с нуля

for row in matrix:
    print(*row)

Сложность. По времени \( O(n^2 + m) \), поскольку один вывод матрицы уже стоит \( O(n^2) \); по памяти \( O(n^2) \).

Задача 3. Обход в глубину

Условие. Задан неориентированный граф. Требуется обойти с помощью DFS все вершины, достижимые из заданной вершины \( s \), и вывести их в порядке обхода. Соседи каждой вершины рассматриваются в порядке возрастания номеров.

Идея решения. Итеративный DFS со стеком, поскольку граф может содержать до \( 10^5 \) вершин, и на длинном пути обхода, например на цепочке, рекурсия, ограниченная тысячей кадров, с этим не справится. Чтобы соседи обрабатывались по возрастанию, поместим их в стек в обратном порядке: снимается всегда последний положенный.

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)                    # граф неориентированный

start = int(input())
for neighbours in graph:
    neighbours.sort(reverse=True)         # сортируем один раз заранее

visited = [False] * (n + 1)
stack, order = [start], []

while stack:
    vertex = stack.pop()
    if visited[vertex]:                   # вершина могла попасть в стек несколько раз
        continue
    visited[vertex] = True
    order.append(vertex)
    for neighbour in graph[vertex]:
        if not visited[neighbour]:
            stack.append(neighbour)

print(*order)

Сложность. По времени \( O(n + m) \) плюс сортировка списков смежности, выполненная заранее; по памяти \( O(n + m) \).

Задача 4. Обход в ширину

Условие. Постановка та же, но обход выполняется в ширину.

Идея решения. Заменим стек на deque и будем снимать элементы с начала; соседей отсортируем уже по возрастанию, а вершину, добавляемую в очередь, сразу пометим посещённой.

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

start = int(input())
for neighbours in graph:
    neighbours.sort()

visited = [False] * (n + 1)
visited[start] = True
queue, order = deque([start]), []

while queue:
    vertex = queue.popleft()              # берём из начала очереди
    order.append(vertex)
    for neighbour in graph[vertex]:
        if not visited[neighbour]:
            visited[neighbour] = True     # помечаем сразу при добавлении
            queue.append(neighbour)

print(*order)

Сложность. Та же, что и у DFS: \( O(n + m) \) по времени и памяти. Коды двух обходов различаются контейнером, порядком перебора соседей и моментом пометки вершины.

Задача 5. Компоненты связности

Условие. Дан неориентированный граф. Требуется найти его компоненты связности: вывести их количество, а затем вершины каждой компоненты по возрастанию. Компоненты упорядочены по номеру первой вершины.

Идея решения. Запустим обход из каждой ещё не посещённой вершины: всё, собранное обходом за один запуск, и есть одна компонента. Если перебирать стартовые вершины по возрастанию, компоненты автоматически получатся в нужном порядке.

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

visited = [False] * (n + 1)
components = []

for vertex in range(1, n + 1):
    if visited[vertex]:
        continue
    component, stack = [], [vertex]       # новая компонента
    while stack:
        current = stack.pop()
        if visited[current]:
            continue
        visited[current] = True
        component.append(current)
        stack.extend(graph[current])
    components.append(sorted(component))

print(len(components))
for component in components:
    print(*component)

Сложность. По времени \( O(n + m) \) плюс сортировка найденных компонент, по памяти \( O(n + m) \). Заметим, что внешний цикл по вершинам, вопреки первому впечатлению, не делает алгоритм квадратичным: каждая вершина обрабатывается по одному разу, а цикл лишь ищет стартовые точки.

Задача 6. Самая дорогая сеть

Условие. Дан взвешенный неориентированный граф. Требуется найти вес максимального остовного дерева — набора рёбер, связывающего все вершины и имеющего наибольший суммарный вес. Если граф несвязен, дерева, натянутого на все вершины, не существует.

Идея решения. Алгоритм Прима, в котором на каждом шаге выбирается не минимальное, а максимальное ребро. Модуль heapq до версии 3.13 включительно реализует лишь min-heap, поэтому в кучу помещается вес со знаком минус: «минимальный» элемент кучи окажется максимальным по модулю.

Начнём с первой вершины и поместим в кучу все рёбра, исходящие из неё. Затем на каждом шаге будем извлекать самое тяжёлое ребро; если оно ведёт в новую вершину, добавим её в остов, прибавим вес к ответу и поместим в кучу её рёбра. Если после завершения цикла в остов вошли не все вершины, значит, граф несвязен.

import heapq

def add_vertex(vertex, graph, added, heap):
    """Добавляет вершину в остов и кладёт её рёбра в кучу."""
    added[vertex] = True
    for neighbour, weight in graph[vertex]:
        if not added[neighbour]:
            heapq.heappush(heap, (-weight, neighbour))   # минус: нужен max-heap

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]

for _ in range(m):
    u, v, weight = map(int, input().split())
    graph[u].append((v, weight))
    graph[v].append((u, weight))

added = [False] * (n + 1)
added[0] = True                           # нулевой вершины не существует
heap, total = [], 0

add_vertex(1, graph, added, heap)         # растим остов из первой вершины
in_tree = 1                               # сколько вершин уже в остове

while in_tree < n and heap:
    weight, vertex = heapq.heappop(heap)
    if not added[vertex]:                 # ребро внутрь остова пропускаем
        total += -weight
        add_vertex(vertex, graph, added, heap)
        in_tree += 1

print(total if in_tree == n else "Oops! I did it again")

Сложность. По времени \( O(m \log n) \), поскольку каждое ребро попадает в кучу не более одного раза, а операции с кучей стоят \( O(\log n) \). По памяти \( O(n + m) \).

Резюме

  • Граф является самой общей структурой, описывающей связи; дерево и список — его частные случаи.
  • Разреженные графы хранятся списком смежности, занимающим \( O(n+m) \) памяти, а плотные матрицей смежности: \( O(n^2) \), зато проверка ребра за \( O(1) \).
  • DFS и BFS отличаются контейнером для вершин — стеком или очередью — и моментом пометки вершины, и оба работают за \( O(n + m) \).
  • BFS находит кратчайшие пути в невзвешенном графе, а алгоритм Дейкстры во взвешенном с неотрицательными весами за \( O(m \log n) \).
  • Посещённые вершины необходимо помечать: в отличие от дерева, у графа есть циклы, и без пометок обход не завершится.
  • Компоненты связности, топологическая сортировка и остовные деревья — три классических применения обходов, к которым сводится множество практических задач.