Графы: BFS, DFS и топологическая сортировка
Графы: BFS, DFS и топологическая сортировка
Графы повсюду: зависимости пакетов, маршруты в сети, социальные связи, порядок миграций.
Словарь
- Граф - набор объектов и связей между ними. Объекты называют вершинами (узлами), связи - рёбрами. V - число вершин, E - число рёбер.
- Ориентированный граф: у ребра есть направление, «A зависит от B» не значит «B зависит от A». Неориентированный: ребро работает в обе стороны, как дружба в соцсети; в списке смежности такое ребро записывают у обеих вершин.
- Соседи вершины - вершины, в которые из неё ведёт ребро.
- Входящая степень вершины - сколько рёбер в неё входит. Для зависимостей это «сколько задач ещё надо сделать до этой».
- Цикл - путь по рёбрам, который возвращается в исходную вершину (A → B → C → A). Ориентированный граф без циклов называют DAG (directed acyclic graph).
- Компонента связности неориентированного графа - группа вершин, между любыми двумя из которых есть путь, и к которой нельзя добавить ни одной вершины. Изолированная вершина без рёбер - отдельная компонента. Посчитать компоненты просто: запускай обход из каждой ещё не посещённой вершины, и число запусков будет ответом.
- Взвешенный граф: у рёбер есть вес (расстояние, время, цена). Невзвешенный - все рёбра «стоят» одинаково.
Представление графа
// Список смежности (adjacency list) - самый частый
type Graph struct {
adjacency map[string][]string
}
func NewGraph() *Graph {
return &Graph{adjacency: make(map[string][]string)}
}
func (g *Graph) AddEdge(from, to string) {
g.adjacency[from] = append(g.adjacency[from], to)
}
<?php
declare(strict_types=1);
final class Graph
{
/** @var array<string, array<string>> */
private array $adjacency = [];
public function addEdge(string $from, string $to): void
{
$this->adjacency[$from][] = $to;
}
/** @return array<string, array<string>> */
public function adjacency(): array
{
return $this->adjacency;
}
}
from collections import defaultdict
# Список смежности (adjacency list) - самый частый
class Graph:
def __init__(self) -> None:
# defaultdict: отсутствующий ключ даёт пустой список,
# как nil-слайс из Go-map
self.adjacency: defaultdict[str, list[str]] = defaultdict(list)
def add_edge(self, from_: str, to: str) -> None:
# from - зарезервированное слово, отсюда подчёркивание
self.adjacency[from_].append(to)
PHP-массив - идеальный adjacency list:
string => array<string>это уже hash map. Никаких отдельных структур не нужно.
Второй способ - матрица смежности V×V: adj[i][j] = true, если есть ребро из i в j. Проверка ребра за O(1), но память O(V²) даже при малом числе рёбер. Список смежности занимает O(V + E), поэтому его берут для разреженных графов (рёбер намного меньше V²: соцсети, зависимости пакетов), а матрицу - для плотных, где почти каждая пара вершин связана.
DFS - обход в глубину
func (g *Graph) DFS(start string) []string {
visited := make(map[string]bool)
var result []string
var dfs func(node string)
dfs = func(node string) {
if visited[node] {
return
}
visited[node] = true
result = append(result, node)
for _, neighbor := range g.adjacency[node] {
dfs(neighbor)
}
}
dfs(start)
return result
}
<?php
declare(strict_types=1);
final class GraphTraversal
{
/** @return array<string> */
public function dfs(Graph $g, string $start): array
{
$visited = [];
$result = [];
$dfs = function (string $node) use (&$dfs, &$visited, &$result, $g): void {
if (isset($visited[$node])) {
return;
}
$visited[$node] = true;
$result[] = $node;
foreach ($g->adjacency()[$node] ?? [] as $neighbor) {
$dfs($neighbor);
}
};
$dfs($start);
return $result;
}
}
class Graph:
...
def dfs(self, start: str) -> list[str]:
visited: set[str] = set()
result: list[str] = []
# Вложенная функция видит visited и result через замыкание
def _dfs(node: str) -> None:
if node in visited:
return
visited.add(node)
result.append(node)
# .get, а не [], чтобы defaultdict не плодил пустые ключи
for neighbor in self.adjacency.get(node, []):
_dfs(neighbor)
_dfs(start)
return result
Замыкание
use (&$dfs, ...)передаёт само себя по ссылке - PHP-эквивалент локальной рекурсивной функции в Go. На очень глубоких графах учитывай лимит рекурсии: с Xdebug этоxdebug.max_nesting_level(512 по умолчанию в Xdebug 3), без него в PHP 8.3+ -zend.max_allowed_stack_size. Для больших графов надёжнее итеративный DFS с явным стеком.
BFS - обход в ширину
BFS идёт по уровням: сначала стартовая вершина, потом все её соседи, потом соседи соседей. Отсюда и применения: кратчайший путь по числу рёбер (ниже), уровни иерархии (прямые подчинённые, их подчинённые), обход сайта краулером «сначала ссылки со стартовой страницы, потом ссылки второго уровня».
func (g *Graph) BFS(start string) []string {
visited := make(map[string]bool)
queue := []string{start}
visited[start] = true
var result []string
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
result = append(result, node)
for _, neighbor := range g.adjacency[node] {
if !visited[neighbor] {
visited[neighbor] = true
queue = append(queue, neighbor)
}
}
}
return result
}
<?php
declare(strict_types=1);
/**
* @return array<string>
*/
function bfs(Graph $g, string $start): array
{
$visited = [$start => true];
$queue = new SplQueue();
$queue->enqueue($start);
$result = [];
while (!$queue->isEmpty()) {
$node = $queue->dequeue();
$result[] = $node;
foreach ($g->adjacency()[$node] ?? [] as $neighbor) {
if (!isset($visited[$neighbor])) {
$visited[$neighbor] = true;
$queue->enqueue($neighbor);
}
}
}
return $result;
}
from collections import deque
class Graph:
...
def bfs(self, start: str) -> list[str]:
visited: set[str] = {start}
# deque: popleft за O(1), list.pop(0) - O(n)
queue: deque[str] = deque([start])
result: list[str] = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in self.adjacency.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
\SplQueueдаёт O(1) dequeue. На голом массиве сarray_shiftкаждое извлечение стоит O(длины очереди) из-за переиндексации, и BFS вырождается в O(V² + E) - не используй его для очереди.
Кратчайший путь (BFS для невзвешенного графа)
func (g *Graph) ShortestPath(start, end string) []string {
visited := make(map[string]bool)
parent := make(map[string]string)
queue := []string{start}
visited[start] = true
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
if node == end {
return buildPath(parent, start, end)
}
for _, neighbor := range g.adjacency[node] {
if !visited[neighbor] {
visited[neighbor] = true
parent[neighbor] = node
queue = append(queue, neighbor)
}
}
}
return nil // путь не найден
}
func buildPath(parent map[string]string, start, end string) []string {
var path []string
for node := end; node != start; node = parent[node] {
path = append([]string{node}, path...)
}
return append([]string{start}, path...)
}
ℹ️ А если у рёбер есть вес?
BFS находит кратчайший путь только по числу рёбер. Если у рёбер есть вес (расстояние, время, цена), он не подходит. Алгоритм Дейкстры с приоритетной очередью находит кратчайшие пути при неотрицательных весах: он каждый раз берёт ближайшую ещё не обработанную вершину и считает её расстояние окончательным. При отрицательных весах это допущение ломается, и Дейкстра может дать неверный ответ. Для таких графов используют алгоритм Беллмана-Форда (Bellman-Ford), он медленнее: O(V * E).
Топологическая сортировка
Используется для определения порядка выполнения задач с зависимостями: вершина попадает в результат только после всех вершин, от которых она зависит. Такой порядок существует только у DAG: если в графе есть цикл, ни одну вершину цикла нельзя поставить первой. Алгоритм ниже (алгоритм Кана) кладёт в очередь вершины с нулевой входящей степенью и, «выполнив» вершину, уменьшает степень её соседей. Если в конце обработаны не все вершины - в графе цикл.
func (g *Graph) TopologicalSort() ([]string, error) {
inDegree := make(map[string]int)
for node := range g.adjacency {
if _, ok := inDegree[node]; !ok {
inDegree[node] = 0
}
for _, neighbor := range g.adjacency[node] {
inDegree[neighbor]++
}
}
var queue []string
for node, degree := range inDegree {
if degree == 0 {
queue = append(queue, node)
}
}
var result []string
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
result = append(result, node)
for _, neighbor := range g.adjacency[node] {
inDegree[neighbor]--
if inDegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
if len(result) != len(inDegree) {
return nil, fmt.Errorf("cycle detected")
}
return result, nil
}
<?php
declare(strict_types=1);
final class CycleException extends RuntimeException {}
/**
* @return array<string>
* @throws CycleException
*/
function topologicalSort(Graph $g): array
{
$adjacency = $g->adjacency();
$inDegree = [];
foreach ($adjacency as $node => $neighbors) {
$inDegree[$node] ??= 0;
foreach ($neighbors as $neighbor) {
$inDegree[$neighbor] = ($inDegree[$neighbor] ?? 0) + 1;
}
}
$queue = new SplQueue();
foreach ($inDegree as $node => $degree) {
if ($degree === 0) {
$queue->enqueue($node);
}
}
$result = [];
while (!$queue->isEmpty()) {
$node = $queue->dequeue();
$result[] = $node;
foreach ($adjacency[$node] ?? [] as $neighbor) {
if (--$inDegree[$neighbor] === 0) {
$queue->enqueue($neighbor);
}
}
}
if (count($result) !== count($inDegree)) {
throw new CycleException('cycle detected');
}
return $result;
}
from collections import deque
class CycleError(Exception):
pass
class Graph:
...
def topological_sort(self) -> list[str]:
in_degree: dict[str, int] = {}
for node, neighbors in self.adjacency.items():
in_degree.setdefault(node, 0)
for neighbor in neighbors:
in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
queue: deque[str] = deque(
node for node, degree in in_degree.items() if degree == 0
)
result: list[str] = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in self.adjacency.get(node, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(in_degree):
# Исключение вместо пары (result, error) из Go
raise CycleError("cycle detected")
return result
У графа обычно много допустимых топологических порядков. В Go-версии начальная очередь строится обходом map, а его порядок случаен, поэтому результат может меняться от запуска к запуску (все варианты корректны). Если нужен детерминированный результат, отсортируй вершины с нулевой входящей степенью: sort.Strings(queue).
В PHP принято бросать типизированный exception вместо tuple
(result, error)- это идиоматичнее для PSR/Symfony-кода. Caller ловитCycleExceptionи решает: лог + 422, retry, или crash.
ℹ️ Где это в реальной жизни
go buildиспользует топологическую сортировку для определения порядка компиляции пакетов. Docker Compose - для порядка запуска сервисов черезdepends_on.