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

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

Графы повсюду: зависимости пакетов, маршруты в сети, социальные связи, порядок миграций.

BFS vs 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.

Зарегистрируйтесь бесплатно, чтобы пройти квиз, решить задание с автопроверкой, вести прогресс.