🌊 DFS - Depth First Search

// Recursive DFS
function dfs(array $graph, int $node, array &$visited = []): array {
    $visited[$node] = true;
    $result = [$node];
    foreach ($graph[$node] ?? [] as $neighbor) {
        if (!isset($visited[$neighbor])) {
            $result = array_merge($result, dfs($graph, $neighbor, $visited));
        }
    }
    return $result;
}

// Iterative DFS (explicit stack)
function dfsIterative(array $graph, int $start): array {
    $visited = [$start => true];
    $stack = [$start]; $result = [];
    while (!empty($stack)) {
        $node = array_pop($stack); // Pop from top
        $result[] = $node;
        foreach (array_reverse($graph[$node] ?? []) as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $stack[] = $neighbor;
            }
        }
    }
    return $result;
}

// Cycle detection in directed graph
function hasCycle(array $graph): bool {
    $WHITE=0; $GRAY=1; $BLACK=2; // 3-color DFS
    $color = array_fill(0, count($graph), $WHITE);

    $dfs = function(int $node) use (&$graph, &$color, &$dfs): bool {
        $color[$node] = $GRAY; // Being processed
        foreach ($graph[$node] ?? [] as $neighbor) {
            if ($color[$neighbor] === $GRAY) return true; // Back edge!
            if ($color[$neighbor]===$WHITE && $dfs($neighbor)) return true;
        }
        $color[$node] = $BLACK;
        return false;
    };

    for ($i = 0; $i < count($graph); $i++) {
        if ($color[$i]===$WHITE && $dfs($i)) return true;
    }
    return false;
}