🔍 PHP Graph Traversal

BFS — Breadth-First Search

BFS explores level by level. Use for shortest path in unweighted graphs.

function bfs(array $graph, int $start): array {
    $visited = [];
    $queue   = [$start];
    $result  = [];
    $visited[$start] = true;

    while (!empty($queue)) {
        $node    = array_shift($queue);
        $result[] = $node;
        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor;
            }
        }
    }
    return $result;
}

Time: O(V + E) | Space: O(V)

---

BFS — Shortest Path (Unweighted)

function shortestPath(array $graph, int $src, int $dst): int {
    $visited = [$src => true];
    $queue   = [[$src, 0]];
    while (!empty($queue)) {
        [$node, $dist] = array_shift($queue);
        if ($node === $dst) return $dist;
        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = [$neighbor, $dist + 1];
            }
        }
    }
    return -1; // not reachable
}

---

DFS — Depth-First Search (Recursive)

function dfs(array $graph, int $node, array &$visited): void {
    $visited[$node] = true;
    echo $node . ' ';
    foreach ($graph[$node] as $neighbor) {
        if (!isset($visited[$neighbor])) {
            dfs($graph, $neighbor, $visited);
        }
    }
}

$visited = [];
dfs($graph, 0, $visited);

Time: O(V + E) | Space: O(V) recursion stack

---

DFS — Iterative

function dfsIterative(array $graph, int $start): array {
    $visited = [];
    $stack   = [$start];
    $result  = [];
    while (!empty($stack)) {
        $node = array_pop($stack);
        if (isset($visited[$node])) continue;
        $visited[$node] = true;
        $result[] = $node;
        foreach ($graph[$node] as $neighbor) {
            if (!isset($visited[$neighbor])) $stack[] = $neighbor;
        }
    }
    return $result;
}

---

Count Connected Components

function countComponents(int $n, array $edges): int {
    $graph = array_fill(0, $n, []);
    foreach ($edges as [$u, $v]) { $graph[$u][] = $v; $graph[$v][] = $u; }

    $visited = [];
    $count   = 0;
    for ($i = 0; $i < $n; $i++) {
        if (!isset($visited[$i])) {
            dfs($graph, $i, $visited);
            $count++;
        }
    }
    return $count;
}

---

Cycle Detection (Directed Graph)

Use three-color marking: white (0) = unvisited, gray (1) = in-stack, black (2) = done.

function hasCycle(array $graph, int $n): bool {
    $color = array_fill(0, $n, 0);
    $dfs = function(int $v) use (&$dfs, &$graph, &$color): bool {
        $color[$v] = 1; // gray — in current path
        foreach ($graph[$v] as $u) {
            if ($color[$u] === 1) return true; // back edge → cycle
            if ($color[$u] === 0 && $dfs($u)) return true;
        }
        $color[$v] = 2; // black — done
        return false;
    };
    for ($i = 0; $i < $n; $i++) {
        if ($color[$i] === 0 && $dfs($i)) return true;
    }
    return false;
}

---

Topological Sort (Kahn's BFS Algorithm)

function topoSort(int $n, array $edges): array {
    $graph   = array_fill(0, $n, []);
    $indegree = array_fill(0, $n, 0);
    foreach ($edges as [$u, $v]) {
        $graph[$u][] = $v;
        $indegree[$v]++;
    }

    $queue = [];
    for ($i = 0; $i < $n; $i++) {
        if ($indegree[$i] === 0) $queue[] = $i;
    }

    $order = [];
    while (!empty($queue)) {
        $node    = array_shift($queue);
        $order[] = $node;
        foreach ($graph[$node] as $neighbor) {
            if (--$indegree[$neighbor] === 0) $queue[] = $neighbor;
        }
    }
    return count($order) === $n ? $order : []; // empty = cycle
}

Time: O(V + E) | Space: O(V)

---

Grid BFS — Island / Flood Fill Pattern

function numIslands(array $grid): int {
    $rows  = count($grid);
    $cols  = count($grid[0]);
    $count = 0;

    $bfs = function(int $r, int $c) use (&$bfs, &$grid, $rows, $cols): void {
        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols || $grid[$r][$c] !== '1') return;
        $grid[$r][$c] = '0'; // mark visited
        $bfs($r+1,$c); $bfs($r-1,$c); $bfs($r,$c+1); $bfs($r,$c-1);
    };

    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($grid[$r][$c] === '1') { $bfs($r, $c); $count++; }
        }
    }
    return $count;
}

Time: O(R × C) | Space: O(R × C)