Graph Algorithms
debt(d9/e5/b3/t7)
Closest to 'silent in production until users hit it' (d9). The detection_hints field explicitly states 'automated: no' and the code_pattern describes hand-rolled implementations of cycle detection, shortest path, etc. No tool in the ecosystem automatically detects wrong algorithm selection (e.g. DFS used instead of BFS for shortest path, or Dijkstra on negative-weight graphs). These bugs only surface at runtime when wrong results are returned or infinite loops are hit on cyclic graphs in production.
Closest to 'touches multiple files / significant refactor in one component' (e5). The quick_fix outlines multiple algorithm swaps (BFS↔DFS, Dijkstra↔Bellman-Ford, adjacency matrix→adjacency list). Swapping a core graph traversal implementation typically requires reworking the data structure representation and the traversal logic together, touching graph construction, traversal, and any downstream consumers of results — more than a one-line patch but generally contained within one component rather than a full cross-cutting refactor.
Closest to 'localised tax' (b3). Graph algorithms typically live in a bounded component (dependency resolver, social feature, route planner). While the choice of algorithm and representation affects that component's correctness and performance, it rarely imposes a tax on the broader codebase. The applies_to scope (web, cli) is wide but the actual graph code tends to be isolated.
Closest to 'serious trap (contradicts how a similar concept works elsewhere)' (t7). The canonical misconception is that 'BFS always finds the shortest path' — which is true for unweighted graphs but false for weighted graphs where Dijkstra is required. Additionally, Dijkstra with negative edge weights produces silently wrong results. These are not minor edge cases: a competent developer familiar with BFS in unweighted contexts will confidently apply it in weighted contexts and get wrong answers, and will apply Dijkstra with negative weights trusting it because the algorithm 'looks right'. Multiple serious traps across the algorithm family justify t7.
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 [];
}