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

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

BFS vs DFS на одном графе: порядок посещения узлов разный

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

// Список смежности (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;
    }
}

PHP-массив - идеальный adjacency list: string => array<string> это уже hash map. Никаких отдельных структур не нужно.

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;
    }
}

Замыкание use (&$dfs, ...) передаёт само себя по ссылке - PHP-эквивалент локальной рекурсивной функции в Go. На очень глубоких графах учитывай xdebug-лимит и xdebug.max_nesting_level (256 по умолчанию).

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;
}

\SplQueue даёт O(1) dequeue. На голом массиве с array_shift 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...)
}

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

Используется для определения порядка выполнения задач с зависимостями.

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;
}

В PHP принято бросать типизированный exception вместо tuple (result, error) - это идиоматичнее для PSR/Symfony-кода. Caller ловит CycleException и решает: лог + 422, retry, или crash.

`go build` использует топологическую сортировку для определения порядка компиляции пакетов. [Docker Compose](../docker/06-docker-compose.md) - для порядка запуска сервисов через `depends_on`.