Graphs — adjacency list, BFS, DFS in PHP

Advanced5 min read·eng-07-006

compare

Concept

Graph: A collection of vertices (nodes) and edges (connections between nodes). Unlike trees, graphs can have cycles, multiple paths between nodes, and disconnected components.

Directed vs Undirected: In a directed graph (digraph), edges have direction (A → B doesn't mean B → A). In an undirected graph, edges are bidirectional.

Weighted vs Unweighted: Edges can have a weight (distance, cost, capacity).

Representations:

Adjacency list: $graph['A'] = ['B', 'C']. Space: O(V + E). Fast to iterate neighbors.
Adjacency matrix: $matrix[i][j] = 1 if edge exists. Space: O(V²). Fast to check if an edge exists. Wasteful for sparse graphs.

BFS (Breadth-First Search):

Uses a queue. Visits all nodes at depth k before depth k+1.
Finds the shortest path in an unweighted graph.
Time: O(V + E).

DFS (Depth-First Search):

Uses a stack (or recursion). Explores as deep as possible before backtracking.
Used for: topological sort, cycle detection, connected components.
Time: O(V + E).

Common problems: Shortest path (BFS for unweighted, Dijkstra for weighted), cycle detection, topological sort (dependency ordering), connected components, graph coloring.

PHP use case: Social network connections, task dependency graphs, route optimization, org chart traversal.

Code Example

php

<?php
// Adjacency list representation (undirected graph)
$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'D', 'E'],
    'C' => ['A', 'F'],
    'D' => ['B'],
    'E' => ['B', 'F'],
    'F' => ['C', 'E'],
];

// BFS — shortest path in unweighted graph
function bfs(array $graph, string $start, string $end): ?array
{
    $queue   = new \SplQueue();
    $visited = [$start => true];
    $parent  = [$start => null];

    $queue->enqueue($start);

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

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

        foreach ($graph[$node] ?? [] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $parent[$neighbor]  = $node;
                $queue->enqueue($neighbor);
            }
        }
    }
    return null; // no path
}

$path = bfs($graph, 'A', 'F');
echo implode(' → ', $path); // A → C → F

// DFS — find all nodes reachable from start
function dfs(array $graph, string $start, array &$visited = []): array
{
    $visited[$start] = true;
    $result = [$start];

    foreach ($graph[$start] ?? [] as $neighbor) {
        if (!isset($visited[$neighbor])) {
            $result = array_merge($result, dfs($graph, $neighbor, $visited));
        }
    }
    return $result;
}

$reachable = dfs($graph, 'A'); // ['A', 'B', 'D', 'E', 'F', 'C']

// Detect cycle in directed graph (DFS with "in-stack" tracking)
function hasCycle(array $graph): bool
{
    $visited = [];
    $inStack = [];

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

        foreach ($graph[$node] ?? [] as $neighbor) {
            if (!isset($visited[$neighbor]) && dfsCheck($neighbor, $graph, $visited, $inStack)) return true;
            if (isset($inStack[$neighbor])) return true; // back edge = cycle
        }

        $inStack[$node] = false;
        return false;
    }

    foreach (array_keys($graph) as $node) {
        if (!isset($visited[$node]) && dfsCheck($node, $graph, $visited, $inStack)) return true;
    }
    return false;
}

// Topological sort (for task dependencies)
function topologicalSort(array $graph): array
{
    $visited = [];
    $stack   = new \SplStack();

    function dfsTopoSort(string $node, array $graph, array &$visited, \SplStack $stack): void {
        $visited[$node] = true;
        foreach ($graph[$node] ?? [] as $dep) {
            if (!isset($visited[$dep])) dfsTopoSort($dep, $graph, $visited, $stack);
        }
        $stack->push($node);
    }

    foreach (array_keys($graph) as $node) {
        if (!isset($visited[$node])) dfsTopoSort($node, $graph, $visited, $stack);
    }

    $result = [];
    while (!$stack->isEmpty()) $result[] = $stack->pop();
    return $result;
}

PreviousHeaps and priority queues — SplMinHeap, SplMaxHeapData Structures in PHP NextSplFixedArray, SplDoublyLinkedList — typed collectionsData Structures in PHP