Graph Algorithms

Also Known As

TL;DR

Explanation

Breadth-First Search (BFS): explores level by level using a queue — finds shortest path in unweighted graphs. Depth-First Search (DFS): explores depth-first using a stack/recursion — detects cycles, topological sort. Dijkstra: shortest path in weighted graphs with non-negative edges. A*: Dijkstra with a heuristic — faster for geographic routing. Topological sort: ordering of nodes with no cycles — dependency resolution, build systems. Applications: social network connections, dependency graphs, route finding, link analysis.

Diagram

flowchart LR
    subgraph BFS_shortest_path
        A1[A] -->|1| B1[B] & C1[C]
        B1 -->|1| D1[D]
        C1 -->|1| D1
        D1 -->|1| E1[E]
    end
    subgraph Dijkstra_weighted
        N1[N1] -->|4| N2[N2]
        N1 -->|2| N3[N3]
        N3 -->|1| N2
        N2 -->|3| N4[N4]
        N3 -->|5| N4
    end
    style A1 fill:#238636,color:#fff
    style E1 fill:#f85149,color:#fff
    style N1 fill:#238636,color:#fff
    style N4 fill:#f85149,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Not tracking visited nodes in BFS/DFS — infinite loops on cyclic graphs.
• Using DFS for shortest path in unweighted graphs — BFS guarantees shortest; DFS does not.
• Dijkstra with negative edge weights — use Bellman-Ford for negative weights; Dijkstra produces wrong results.
• Adjacency matrix for sparse graphs — wastes O(V²) memory; adjacency list is O(V+E) and usually correct.

Code Examples

// DFS for shortest path — wrong result on unweighted graph:
function findPath(array $graph, string $start, string $end): array {
    $visited = [];
    $stack = [[$start, [$start]]];
    while ($stack) {
        [$node, $path] = array_pop($stack); // DFS — may not find shortest path
        if ($node === $end) return $path;
        foreach ($graph[$node] as $neighbour) {
            if (!in_array($neighbour, $visited)) {
                $visited[] = $neighbour;
                $stack[] = [$neighbour, [...$path, $neighbour]];
            }
        }
    }
    return [];
}

// BFS — guaranteed shortest path in unweighted graph:
function shortestPath(array $graph, string $start, string $end): array {
    $queue = [[$start, [$start]]];
    $visited = [$start => true];
    while ($queue) {
        [$node, $path] = array_shift($queue); // BFS uses queue, not stack
        if ($node === $end) return $path;
        foreach ($graph[$node] ?? [] as $neighbour) {
            if (!isset($visited[$neighbour])) {
                $visited[$neighbour] = true;
                $queue[] = [$neighbour, [...$path, $neighbour]];
            }
        }
    }
    return [];
}

References

• ↗ https://en.wikipedia.org/wiki/Graph_traversal

Tags

Related Terms