Графы

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

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

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

Определения

Граф \( 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 v) \) вместо \( O(1) \).

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

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

Обходы графа

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

Поиск в глубину (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 естественно записывается через рекурсию и применяется для поиска циклов, топологической сортировки, компонент связности и анализа структуры графа.

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

В невзвешенном графе кратчайший путь находит 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) \). Веса обязаны быть неотрицательными: на отрицательных рёбрах жадная стратегия перестаёт работать, и требуется алгоритм Беллмана — Форда.

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

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

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

def topological_sort(graph, vertices):
    """Топологическая сортировка ориентированного ациклического графа."""
    visited = set()
    order = []

    def visit(vertex):
        visited.add(vertex)
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                visit(neighbour)
        order.append(vertex)      # добавляем на выходе из вершины

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

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

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

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

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

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

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

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

Для практических расчётов реализовывать алгоритмы вручную не обязательно: готовые собраны в библиотеке 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 реализует лишь 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) \).
• Посещённые вершины необходимо помечать: в отличие от дерева, у графа есть циклы, и без пометок обход не завершится.
• Компоненты связности, топологическая сортировка и остовные деревья — три классических применения обходов, к которым сводится множество практических задач.