Обходы в ширину и глубину, топологическая сортировка, Дейкстра и A*, union-find и остовные деревья. Как они устроены, где работают в сетях, сборщиках мусора и пакетных менеджерах — и как узнать графовую задачу на собеседовании.
Листайте стрелками ← →, свайпом или кнопками внизу. В схемах нажимайте кнопки и клетки.
Граф — это вершины и рёбра между ними. Рёбра бывают направленными или нет, с весами или без. Половина инфраструктуры — графы, их просто так не называют.
Нажмите на пример: что в нём вершины, что рёбра и какой алгоритм там работает.
(u, v, w). Так граф лежит в таблице базы и так его ест алгоритм Крускала.Большие графы хранят в CSR: один массив смещений и один массив соседей — без объекта на каждую вершину.
BFS идёт слоями: сначала все вершины на расстоянии 1, потом 2 и так далее. Поэтому первое попадание в вершину — кратчайший путь по числу рёбер.
from collections import deque
def bfs(start, goal):
q, prev = deque([start]), {start: None}
while q:
cur = q.popleft()
if cur == goal:
return path(prev, goal)
for nxt in neighbours(cur):
# метим при постановке
if nxt not in prev:
prev[nxt] = cur
q.append(nxt)
O(V + E). Очередь — deque: list.pop(0) сдвигает весь список и превращает обход в O(V²).
DFS идёт вглубь, пока может, а потом откатывается. Его стек — стек вызовов. Три цвета вершин: белая — не видели, серая — на стеке, чёрная — закончена. Ребро в серую вершину — цикл.
def dfs(u):
color[u] = GREY
for v in graph[u]:
if color[v] == GREY: # обратное ребро
raise CycleError(u, v)
if color[v] == WHITE:
dfs(v)
color[u] = BLACK
order.append(u) # порядок выхода
Так ищут дедлоки: цикл в графе «кто кого ждёт». Postgres через deadlock_timeout строит такой граф и отменяет одну транзакцию — подробнее в презентации про синхронизацию.
Запускаем обход из каждой ещё не посещённой вершины. Сколько запусков — столько компонент. Сетка — тоже граф: клетка — вершина, соседи — клетки по сторонам.
Лабиринт 2000 × 2000 клеток почти без стен. Путь ищут рекурсивным DFS на Python с visited. Что произойдёт?
sys.setrecursionlimit опасно: до Python 3.11 кончается стек потока и процесс падает с segfault. В Java будет StackOverflowError. Пишите обход с явным стеком — и помните, что DFS вообще не гарантирует кратчайший путь.Порядок, в котором каждая задача идёт после своих зависимостей. Он существует, только если в графе нет циклов (DAG).
Алгоритм Кана: считаем у каждой вершины входящие рёбра, кладём в очередь вершины с нулём, берём их по одной и уменьшаем счётчики соседей. Не все вершины вышли — значит, остался цикл. Всё, что одновременно лежит в очереди, можно собирать параллельно.
На схеме стрелка X → Y значит «X собирается раньше Y», число в кружке — сколько зависимостей ещё не собрано.
dependencies, Alembic — down_revision. Две «головы» — это две вершины без потомков, их сводят merge-миграцией.
from graphlib import TopologicalSorter # Python 3.9+
deps = {"app": ["web", "db"], "web": ["http", "json"],
"db": ["driver"], "http": ["socket"],
"driver": ["socket"]}
list(TopologicalSorter(deps).static_order())
# ['json', 'socket', 'http', 'driver', 'web', 'db', 'app']
ts = TopologicalSorter(deps)
ts.prepare()
while ts.is_active():
batch = ts.get_ready() # готовы параллельно
run_all(batch)
ts.done(*batch)
# ('json', 'socket') → ('http', 'driver')
# → ('web', 'db') → ('app',)
# цикл → graphlib.CycleError с примером цикла
Достаём из кучи вершину с наименьшим известным расстоянием — оно уже окончательное. Потом релаксируем её рёбра: если через неё до соседа короче, обновляем расстояние.
import heapq
def dijkstra(g, src):
dist, heap = {src: 0}, [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # устаревшая запись
for v, w in g[u]:
nd = d + w
if nd < dist.get(v, inf):
dist[v] = nd
heapq.heappush(heap, (nd, v))
return dist
O((V + E) log V). В heapq нет «уменьшить ключ», поэтому кладут дубликат и пропускают устаревшие записи. Так считает маршруты OSPF: каждый роутер знает всю карту сети и запускает Дейкстру (про сети).
Дейкстра закрывает вершину, как только достал её из кучи. Отрицательное ребро может потом сделать путь короче, но закрытую вершину никто не пересмотрит.
−log(курс) превращают поиск валютного арбитража в поиск такого цикла.A* сортирует кучу по g + h: пройденное расстояние плюс оценка остатка. Если оценка не преувеличивает (манхэттенское расстояние на сетке, прямая на карте), путь оптимален, а просмотренных вершин в разы меньше.
Завысьте оценку — поиск станет жадным: ещё быстрее, но путь может оказаться длиннее. Навигаторы на графе дорог континента ещё и готовят граф заранее (contraction hierarchies в OSRM): ответ за миллисекунды вместо секунд.
Сетка, где переход по дороге стоит 0, а через стену — 1 (ломаем стену). Нужно минимальное число сломанных стен. Что выбрать?
Массив parent: элемент указывает на родителя, корень — представитель множества. find идёт к корню, union подвешивает корень к корню.
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # сжатие
x = parent[x]
return x
def union(a, b):
a, b = find(a), find(b)
if a == b:
return False # уже вместе
if rank[a] < rank[b]:
a, b = b, a # низкое — под высокое
parent[b] = a
rank[a] += rank[a] == rank[b]
return True
С обеими оптимизациями — почти O(1) на операцию. Применения: Крускал, связность сети по мере добавления линков, склейка аккаунтов, вывод типов в компиляторах.
Связать все вершины самым дешёвым набором рёбер. Алгоритм Крускала сортирует рёбра по весу и берёт ребро, если оно соединяет разные компоненты, — это проверяет union-find. O(E log E).
STP в Ethernet тоже строит остовное дерево, чтобы не было петель, но другое: кратчайших путей до корневого коммутатора.
Граф двудольный, если вершины можно покрасить в два цвета так, чтобы каждое ребро соединяло разные цвета. Проверка — BFS с раскраской: сосед получает противоположный цвет. Конфликт означает цикл нечётной длины.
Граф не обязан лежать в памяти. Вершина — состояние, ребро — допустимый ход, соседей генерируем на лету. «Минимальное число ходов» — значит, BFS по состояниям.
cold → cord → card → ward → warm, по одной букве за ход.Двунаправленный BFS идёт навстречу с обоих концов: вместо bd состояний — около 2·bd/2.
def ladder(begin, end, words):
# «c_ld» → [cold, cord…]: соседи без перебора всех пар
buckets = defaultdict(list)
for w in words:
for i in range(len(w)):
buckets[w[:i] + "_" + w[i+1:]].append(w)
q, seen = deque([(begin, 1)]), {begin}
while q:
w, d = q.popleft()
if w == end:
return d
for i in range(len(w)):
for nxt in buckets[w[:i] + "_" + w[i+1:]]:
if nxt not in seen:
seen.add(nxt)
q.append((nxt, d + 1))
return 0
Пользователь кликает по случайным ссылкам, а с вероятностью 15% прыгает на случайную страницу. PageRank — доля времени, которую он проводит на странице. Ссылка с важной страницы весит больше, чем с безвестной.
def pagerank(links, d=0.85, iters=50):
# links: {страница: [на кого ссылается]}
n = len(links)
rank = {p: 1 / n for p in links}
for _ in range(iters):
new = {p: (1 - d) / n for p in links}
for p, outs in links.items():
if not outs: # тупик: раздаём всем
for q in new:
new[q] += d * rank[p] / n
for q in outs:
new[q] += d * rank[p] / len(outs)
rank = new
return rank
Начните с вопросов: направленный ли граф, есть ли веса и какие, сколько вершин, может ли он быть несвязным. Скажите сложность — почти всегда O(V + E). Типичные ошибки: отмечать visited при извлечении из очереди вместо постановки, забыть про несвязные части, рекурсия на большом входе.
Мониторинг получает поток событий «узел A соединён с узлом B» — 10 млн узлов, сотни тысяч событий в секунду. После каждого события нужно знать, сколько в сети изолированных кластеров.
union. Ограничение: удаление связей он не поддерживает.
# графы зависимостей
$ pipdeptree -r -p urllib3 # кто тянет пакет
$ npm explain lodash
$ go mod graph | grep x/net
$ bazel query 'rdeps(//..., //lib:db)'
$ terraform graph | dot -Tsvg > infra.svg
# маршруты: какой путь выбрала сеть
$ traceroute -n example.com # или mtr
# кто кого ждёт в Postgres (граф ожиданий)
SELECT pid, pg_blocking_pids(pid), query
FROM pg_stat_activity
WHERE cardinality(pg_blocking_pids(pid)) > 0;
# Python: не пишите сами, если не собеседование
import networkx as nx
G = nx.DiGraph([("a", "b", {"w": 3}), …])
nx.shortest_path(G, "a", "z", weight="w")
nx.find_cycle(G); list(nx.topological_sort(G))
# большие графы — scipy.sparse.csgraph, igraph
-- иерархии в SQL: обход рекурсивным CTE
WITH RECURSIVE sub AS (
SELECT id FROM employees WHERE id = 42
-- UNION без ALL отбрасывает повторы:
-- цикл в данных не зациклит запрос
UNION
SELECT e.id FROM employees e
JOIN sub ON e.manager_id = sub.id)
SELECT count(*) FROM sub;
Граф в памяти: list of lists или CSR вместо dict объектов, если вершин миллионы. Многошаговые обходы как основной запрос — повод посмотреть на графовую базу (Neo4j), но для деревьев и иерархий хватает рекурсивного CTE в Postgres.
graphlib). Цикл в графе зависимостей — ошибка, в графе ожиданий — дедлок.Задача про «минимальное число шагов» — это BFS, пока не доказано обратное.