BFS and DFS – graph traversal, shortest path, cycle detection

BFS and DFS are fundamental graph traversal algorithms. They appear in unexpected places in web development: finding the shortest path between categories in a tree, detecting circular dependencies between modules, or checking if two nodes in a social graph are connected. I implement both in PHP with practical examples.

Graph representation in PHP

<?php

// Adjacency list - efficient for sparse graphs (most real-world cases)
$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'D', 'E'],
    'C' => ['A', 'F'],
    'D' => ['B'],
    'E' => ['B', 'F'],
    'F' => ['C', 'E'],
];
// A connects to B and C, B connects to A, D and E, etc.

BFS – Breadth-First Search

BFS explores the graph level by level using a queue. Guarantees finding the shortest path in an unweighted graph.

<?php

declare(strict_types=1);

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

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

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

        foreach ($graph[$node] ?? [] as $neighbour) {
            if (!isset($visited[$neighbour])) {
                $visited[$neighbour] = true;
                $queue->enqueue($neighbour);
            }
        }
    }

    return $order;
}

$result = bfs($graph, 'A');
print_r($result); // ['A', 'B', 'C', 'D', 'E', 'F'] - level by level

// Shortest path with BFS
function shortestPath(array $graph, string $start, string $end): ?array
{
    if ($start === $end) return [$start];

    $queue    = new \SplQueue();
    $visited  = [$start => true];
    $parents  = [$start => null];

    $queue->enqueue($start);

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

        foreach ($graph[$node] ?? [] as $neighbour) {
            if (isset($visited[$neighbour])) continue;

            $visited[$neighbour]  = true;
            $parents[$neighbour]  = $node;

            if ($neighbour === $end) {
                // Reconstruct path
                $path = [];
                $current = $end;
                while ($current !== null) {
                    array_unshift($path, $current);
                    $current = $parents[$current];
                }
                return $path;
            }

            $queue->enqueue($neighbour);
        }
    }

    return null; // no path found
}

$path = shortestPath($graph, 'A', 'F');
print_r($path); // ['A', 'C', 'F'] - 2 steps, shortest route

DFS – Depth-First Search

DFS explores as deep as possible before backtracking. Naturally implemented recursively, or iteratively with a stack.

<?php

declare(strict_types=1);

// Recursive DFS
function dfsRecursive(array $graph, string $node, array &$visited = []): array
{
    $visited[$node] = true;
    $order          = [$node];

    foreach ($graph[$node] ?? [] as $neighbour) {
        if (!isset($visited[$neighbour])) {
            $order = array_merge($order, dfsRecursive($graph, $neighbour, $visited));
        }
    }

    return $order;
}

// Iterative DFS (avoids deep recursion)
function dfsIterative(array $graph, string $start): array
{
    $visited = [];
    $stack   = new \SplStack();
    $order   = [];

    $stack->push($start);

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

        if (isset($visited[$node])) continue;
        $visited[$node] = true;
        $order[]        = $node;

        // Push neighbours in reverse order to maintain left-to-right traversal
        foreach (array_reverse($graph[$node] ?? []) as $neighbour) {
            if (!isset($visited[$neighbour])) {
                $stack->push($neighbour);
            }
        }
    }

    return $order;
}

$resultDfs = dfsIterative($graph, 'A');
print_r($resultDfs); // ['A', 'B', 'D', 'E', 'F', 'C'] - depth first

Cycle detection with DFS

<?php

// Detect circular dependencies between Magento modules
function hasCycle(array $dependencies): bool
{
    $visited    = [];
    $inProgress = [];

    function dfsHasCycle(string $node, array $deps, array &$visited, array &$inProgress): bool
    {
        $visited[$node]    = true;
        $inProgress[$node] = true;

        foreach ($deps[$node] ?? [] as $dep) {
            if (!isset($visited[$dep])) {
                if (dfsHasCycle($dep, $deps, $visited, $inProgress)) {
                    return true;
                }
            } elseif (isset($inProgress[$dep])) {
                return true; // back edge - cycle found
            }
        }

        unset($inProgress[$node]);
        return false;
    }

    foreach (array_keys($dependencies) as $node) {
        if (!isset($visited[$node])) {
            if (dfsHasCycle($node, $dependencies, $visited, $inProgress)) {
                return true;
            }
        }
    }

    return false;
}

// Example: module dependencies
$deps = [
    'ModuleA' => ['ModuleB', 'ModuleC'],
    'ModuleB' => ['ModuleD'],
    'ModuleC' => ['ModuleD'],
    'ModuleD' => [],
    // 'ModuleD' => ['ModuleA'],  // this would create a cycle
];

echo hasCycle($deps) ? 'Circular dependency detected!' : 'No cycles - OK';

BFS vs DFS – when to use which

Summary

BFS and DFS are not just academic exercises – they appear in real projects whenever you work with hierarchical data (category trees), dependency graphs (module loading order), or network structures (related products). BFS guarantees the shortest path in unweighted graphs; DFS is natural for cycle detection and topological sorting. Both run in O(V + E) time – vertices plus edges.