BFS i DFS – przeszukiwanie grafów, najkrótsza ścieżka, wykrywanie cykli

Grafy to struktury danych, które pojawiają się w zaskakujących miejscach: drzewo kategorii w Magento, zależności między modułami, sieć powiązanych produktów, routing w aplikacjach. BFS i DFS to dwa fundamentalne algorytmy przeszukiwania grafów. Implementuję oba w PHP i pokazuję gdzie realnie je stosuję.

Reprezentacja grafu w PHP

Graf można reprezentować na dwa podstawowe sposoby. Lista sąsiedztwa jest zwykle bardziej praktyczna przy rzadkich grafach:

<?php

declare(strict_types=1);

class Graph
{
    private array $adjacencyList = [];
    private bool $directed;

    public function __construct(bool $directed = false)
    {
        $this->directed = $directed;
    }

    public function addVertex(string $vertex): void
    {
        if (!isset($this->adjacencyList[$vertex])) {
            $this->adjacencyList[$vertex] = [];
        }
    }

    public function addEdge(string $from, string $to, int $weight = 1): void
    {
        $this->addVertex($from);
        $this->addVertex($to);

        $this->adjacencyList[$from][] = ['vertex' => $to, 'weight' => $weight];

        if (!$this->directed) {
            $this->adjacencyList[$to][] = ['vertex' => $from, 'weight' => $weight];
        }
    }

    public function getNeighbors(string $vertex): array
    {
        return array_column($this->adjacencyList[$vertex] ?? [], 'vertex');
    }

    public function getVertices(): array
    {
        return array_keys($this->adjacencyList);
    }
}

// Przykład: drzewo kategorii Magento jako graf
$categoryGraph = new Graph(directed: true);
$categoryGraph->addEdge('Root', 'Elektronika');
$categoryGraph->addEdge('Root', 'Odzież');
$categoryGraph->addEdge('Elektronika', 'Telefony');
$categoryGraph->addEdge('Elektronika', 'Laptopy');
$categoryGraph->addEdge('Telefony', 'Smartfony');
$categoryGraph->addEdge('Telefony', 'Akcesoria');
$categoryGraph->addEdge('Odzież', 'Meska');
$categoryGraph->addEdge('Odzież', 'Damska');

BFS – Breadth-First Search (wszerz)

BFS przeszukuje graf poziomami – najpierw wszystkich sąsiadów węzła startowego, potem sąsiadów sąsiadów itd. Używa kolejki (FIFO). Gwarantuje znalezienie najkrótszej ścieżki w grafie bez wag:

<?php

declare(strict_types=1);

function bfs(Graph $graph, string $start): array
{
    $visited = [];
    $queue   = new \SplQueue();
    $order   = [];

    $queue->enqueue($start);
    $visited[$start] = true;

    while (!$queue->isEmpty()) {
        $vertex  = $queue->dequeue();
        $order[] = $vertex;

        foreach ($graph->getNeighbors($vertex) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }

    return $order;
}

// BFS po drzewie kategorii od Root
$traversal = bfs($categoryGraph, 'Root');
// ['Root', 'Elektronika', 'Odzież', 'Telefony', 'Laptopy', 'Meska', 'Damska', 'Smartfony', 'Akcesoria']
// Kategorie posortowane wg odległości od Root - poziomami

Znajdowanie najkrótszej ścieżki przez BFS:

<?php

function shortestPath(Graph $graph, string $start, string $end): ?array
{
    if ($start === $end) {
        return [$start];
    }

    $visited = [];
    $queue   = new \SplQueue();
    $parent  = []; // zapamiętaj skąd dotarłeś do każdego węzła

    $queue->enqueue($start);
    $visited[$start] = true;

    while (!$queue->isEmpty()) {
        $vertex = $queue->dequeue();

        foreach ($graph->getNeighbors($vertex) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $parent[$neighbor]  = $vertex;
                $queue->enqueue($neighbor);

                if ($neighbor === $end) {
                    // Odbuduj ścieżkę idąc od końca do początku
                    $path = [];
                    $node = $end;

                    while ($node !== $start) {
                        array_unshift($path, $node);
                        $node = $parent[$node];
                    }
                    array_unshift($path, $start);

                    return $path;
                }
            }
        }
    }

    return null; // brak ścieżki
}

$path = shortestPath($categoryGraph, 'Root', 'Smartfony');
// ['Root', 'Elektronika', 'Telefony', 'Smartfony']

DFS – Depth-First Search (w głąb)

DFS idzie jak najgłębiej w jedną gałąź zanim cofnie się i sprawdzi kolejną. Używa stosu (LIFO) – iteracyjnie lub rekurencyjnie:

<?php

// DFS iteracyjny - używa SplStack
function dfsIterative(Graph $graph, string $start): array
{
    $visited = [];
    $stack   = new \SplStack();
    $order   = [];

    $stack->push($start);

    while (!$stack->isEmpty()) {
        $vertex = $stack->pop();

        if (isset($visited[$vertex])) {
            continue;
        }

        $visited[$vertex] = true;
        $order[]          = $vertex;

        // Wrzuć sąsiadów na stos w odwrotnej kolejności
        // żeby przetwarzać ich w naturalnej kolejności
        foreach (array_reverse($graph->getNeighbors($vertex)) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $stack->push($neighbor);
            }
        }
    }

    return $order;
}

// DFS rekurencyjny - prostszy w zapisie
function dfsRecursive(Graph $graph, string $vertex, array &$visited = [], array &$order = []): array
{
    $visited[$vertex] = true;
    $order[]          = $vertex;

    foreach ($graph->getNeighbors($vertex) as $neighbor) {
        if (!isset($visited[$neighbor])) {
            dfsRecursive($graph, $neighbor, $visited, $order);
        }
    }

    return $order;
}

$dfsOrder = dfsIterative($categoryGraph, 'Root');
// ['Root', 'Elektronika', 'Telefony', 'Smartfony', 'Akcesoria', 'Laptopy', 'Odzież', 'Meska', 'Damska']
// Idzie w głąb - najpierw cała gałąź Elektronika przed Odzieżą

Wykrywanie cykli – zależności między modułami

DFS świetnie nadaje się do wykrywania cykli w grafie skierowanym – np. cyklicznych zależności między modułami:

<?php

function hasCycle(Graph $graph): bool
{
    $visited    = [];
    $inStack    = []; // węzły aktualnie na stosie rekurencji

    $dfsCheck = function(string $vertex) use ($graph, &$visited, &$inStack, &$dfsCheck): bool {
        $visited[$vertex] = true;
        $inStack[$vertex] = true;

        foreach ($graph->getNeighbors($vertex) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                if ($dfsCheck($neighbor)) {
                    return true; // cykl wykryty głębiej
                }
            } elseif (isset($inStack[$neighbor])) {
                return true; // krawędź do węzła na aktualnym stosie = cykl
            }
        }

        unset($inStack[$vertex]);
        return false;
    };

    foreach ($graph->getVertices() as $vertex) {
        if (!isset($visited[$vertex])) {
            if ($dfsCheck($vertex)) {
                return true;
            }
        }
    }

    return false;
}

// Sprawdź czy moduły mają cykliczne zależności
$moduleGraph = new Graph(directed: true);
$moduleGraph->addEdge('ModuleA', 'ModuleB');
$moduleGraph->addEdge('ModuleB', 'ModuleC');
$moduleGraph->addEdge('ModuleC', 'ModuleA'); // cykl!

var_dump(hasCycle($moduleGraph)); // true

Kiedy BFS, kiedy DFS?

Podsumowanie

BFS i DFS to algorytmy które warto mieć w głowie nawet jeśli nie implementujesz grafów codziennie. Drzewo kategorii Magento, zależności modułów w module.xml, hierarchia uprawnień ACL – to wszystko grafy. Znajomość BFS i DFS pozwala myśleć o tych strukturach w kategoriach algorytmicznych i dobierać właściwe narzędzie gdy pojawi się problem z przeszukiwaniem lub sortowaniem hierarchii.