Графы: BFS, DFS и топологическая сортировка

Граф — это узлы и связи; всё, что про зависимости и маршруты, сводится к графам.

Граф — множество вершин и рёбер между ними; топологическая сортировка — порядок вершин, при котором каждое ребро ведёт от более раннего узла к более позднему.

Представление графа

Чаще всего граф хранят списком смежности: для каждой вершины — список её соседей. Это экономно для разреженных графов.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": []
}
for node, neighbors in graph.items():
    print(node, "->", neighbors)

Вывод:

A -> ['B', 'C']
B -> ['D']
C -> ['D']
D -> []

BFS по графу

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

from collections import deque

def bfs(graph, start):
    visited = set([start])
    q = deque([start])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs(graph, "A"))

Вывод:

['A', 'B', 'C', 'D']

Топологическая сортировка (алгоритм Кана)

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

from collections import deque

def topo_sort(graph):
    indeg = {node: 0 for node in graph}
    for node in graph:
        for nb in graph[node]:
            indeg[nb] += 1
    q = deque([n for n in graph if indeg[n] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nb in graph[node]:
            indeg[nb] -= 1
            if indeg[nb] == 0:
                q.append(nb)
    return order if len(order) == len(graph) else []

graph = {"shtany": ["botinki"], "noski": ["botinki"], "botinki": []}
print(topo_sort(graph))

Вывод:

['shtany', 'noski', 'botinki']

Как работает под капотом

BFS и DFS на графе обязательно используют visited, иначе цикл приведёт к бесконечному обходу. Топосорт Кана работает так: вершина без входящих рёбер не зависит ни от кого — её можно поставить первой. Удаляя её, мы уменьшаем входящие степени соседей; те, у кого степень обнулилась, становятся «готовыми». Если в конце обработаны не все вершины — в графе есть цикл, и топологического порядка не существует (мы возвращаем пустой список). Сложность — O(V + E).

Частые ошибки

• Забыть visited — обход зациклится на циклическом графе.
• Не обработать обнаружение цикла в топосорте (проверка len(order) == len(graph)).
• Путать ориентированный и неориентированный граф — в топосорте рёбра направленные.

Итог

• Граф удобно хранить списком смежности; обходы требуют visited.
• BFS — вширь, DFS — вглубь; оба за O(V + E).
• Топосорт Кана упорядочивает зависимости и заодно ловит циклы.