--- # === IDENTITY === id: software/patterns/graph-algorithms/2026 canonical_question: "What are the essential graph algorithms (BFS, DFS, Dijkstra, A*)?" aliases: - "graph traversal algorithms BFS DFS" - "shortest path algorithm Dijkstra Bellman-Ford" - "minimum spanning tree Kruskal Prim" - "A* pathfinding algorithm heuristic search" - "strongly connected components Tarjan Kosaraju" - "topological sort DAG ordering" entity_type: software_reference domain: software > patterns > graph_algorithms region: global jurisdiction: global temporal_scope: 1956-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Dijkstra's algorithm requires non-negative edge weights; use Bellman-Ford for graphs with negative edges" - "A* requires an admissible heuristic (never overestimates) to guarantee optimal paths" - "Topological sort is only defined for directed acyclic graphs (DAGs); cyclic graphs have no valid ordering" - "Floyd-Warshall has O(V^3) time and O(V^2) space — impractical for graphs with more than ~5,000 nodes" - "BFS finds shortest paths only in unweighted graphs; do not use BFS for weighted shortest-path problems" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Need to solve network flow or matching problems (max-flow, min-cut, bipartite matching)" use_instead: "Network flow algorithms (Ford-Fulkerson, Hopcroft-Karp)" - condition: "Working with probabilistic or Bayesian graph models" use_instead: "Probabilistic graphical models / Bayesian network inference" # === AGENT HINTS === inputs_needed: - key: graph_type question: "What type of graph are you working with?" type: choice options: ["directed", "undirected", "weighted", "DAG"] - key: problem_type question: "What problem are you trying to solve?" type: choice options: ["shortest path", "traversal", "MST", "cycle detection", "topological ordering", "connected components"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/graph-algorithms/2026" suggested_citation: "Source: knowledgelib.io — AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/topological-sort/2026" label: "Topological Sort" - id: "software/patterns/dynamic-programming/2026" label: "Dynamic Programming Patterns" - id: "software/patterns/sorting-algorithms/2026" label: "Sorting Algorithms" - id: "software/patterns/union-find-disjoint-set/2026" label: "Union-Find / Disjoint Set" solves: [] alternative_to: [] often_confused_with: [] # === SOURCES === sources: - id: src1 title: "Introduction to Algorithms (CLRS), 4th Edition — Graph Algorithms Chapters 20-26" author: Cormen, Leiserson, Rivest, Stein url: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ type: academic_paper published: 2022-04-05 reliability: authoritative - id: src2 title: "Breadth First Search — CP-Algorithms" author: CP-Algorithms url: https://cp-algorithms.com/graph/breadth-first-search.html type: community_resource published: 2024-01-15 reliability: high - id: src3 title: "Depth First Search — CP-Algorithms" author: CP-Algorithms url: https://cp-algorithms.com/graph/depth-first-search.html type: community_resource published: 2024-01-15 reliability: high - id: src4 title: "Dijkstra's algorithm — Wikipedia" author: Wikipedia url: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm type: community_resource published: 2025-12-01 reliability: moderate_high - id: src5 title: "Graph Data Structure and Algorithms — GeeksforGeeks" author: GeeksforGeeks url: https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/ type: community_resource published: 2025-06-01 reliability: moderate_high - id: src6 title: "Kruskal's algorithm — Wikipedia" author: Wikipedia url: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm type: community_resource published: 2025-10-01 reliability: moderate_high - id: src7 title: "Tarjan's strongly connected components algorithm — Wikipedia" author: Wikipedia url: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm type: community_resource published: 2025-09-01 reliability: moderate_high - id: src8 title: "Bellman-Ford Algorithm — GeeksforGeeks" author: GeeksforGeeks url: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ type: community_resource published: 2025-08-01 reliability: moderate_high --- # Essential Graph Algorithms: Complete Reference ## TL;DR - **Bottom line**: The essential graph algorithms are BFS and DFS for traversal, Dijkstra and Bellman-Ford for shortest paths, A* for heuristic search, Floyd-Warshall for all-pairs shortest paths, Kruskal and Prim for minimum spanning trees, topological sort for DAG ordering, and Tarjan/Kosaraju for strongly connected components. - **Key tool/command**: `from collections import deque; deque() for BFS, heapq for Dijkstra` - **Watch out for**: Using Dijkstra on graphs with negative edge weights — it produces incorrect results silently. - **Works with**: Any language with arrays, queues, and priority queues. Language-agnostic algorithms dating to 1956. ## Constraints - Dijkstra's algorithm requires non-negative edge weights; use Bellman-Ford for graphs with negative edges [src4] - A* requires an admissible heuristic (h(n) <= actual cost) to guarantee optimal shortest paths [src1] - Topological sort is only defined for DAGs; if the graph has cycles, no valid ordering exists [src1] - Floyd-Warshall uses O(V^3) time and O(V^2) space — impractical for V > ~5,000 [src1] - BFS only finds shortest paths in unweighted or unit-weight graphs; for weighted graphs, use Dijkstra or Bellman-Ford [src2] ## Quick Reference | Algorithm | Problem | Time Complexity | Space | Graph Type | Negative Weights | |---|---|---|---|---|---| | BFS | Traversal / Shortest path (unweighted) | O(V + E) | O(V) | Directed / Undirected | N/A | | DFS | Traversal / Cycle detection / Topological sort | O(V + E) | O(V) | Directed / Undirected | N/A | | Dijkstra (binary heap) | Single-source shortest path | O((V + E) log V) | O(V) | Weighted, non-negative | No | | Dijkstra (Fibonacci heap) | Single-source shortest path | O(E + V log V) | O(V) | Weighted, non-negative | No | | Bellman-Ford | Single-source shortest path | O(V * E) | O(V) | Weighted (any) | Yes (detects negative cycles) | | A* | Single-pair shortest path (heuristic) | O(E) best, O(V!) worst | O(V) | Weighted, non-negative | No | | Floyd-Warshall | All-pairs shortest path | O(V^3) | O(V^2) | Weighted (any) | Yes (detects negative cycles) | | Kruskal | Minimum spanning tree | O(E log E) | O(V) | Undirected, weighted | Yes | | Prim (binary heap) | Minimum spanning tree | O((V + E) log V) | O(V) | Undirected, weighted | Yes | | Topological Sort (Kahn's) | DAG linear ordering | O(V + E) | O(V) | Directed acyclic (DAG) | N/A | | Tarjan SCC | Strongly connected components | O(V + E) | O(V) | Directed | N/A | | Kosaraju SCC | Strongly connected components | O(V + E) | O(V) | Directed | N/A | ## Decision Tree > Full script: [decision-tree.txt](scripts/decision-tree.txt) (36 lines) ``` START: What problem are you solving? ├── Shortest path? │ ├── Single source? │ │ ├── Unweighted graph? │ │ │ └── YES → BFS (O(V+E)) # ... (see full script) ``` ## Step-by-Step Guide ### 1. Represent the graph with an adjacency list An adjacency list is the standard representation for most graph algorithms. It uses O(V + E) space and supports efficient neighbor iteration. Adjacency matrices use O(V^2) space and are only preferred for dense graphs or when O(1) edge-existence queries are needed. [src1] ```python from collections import defaultdict # Unweighted graph graph = defaultdict(list) edges = [(0, 1), (0, 2), (1, 3), (2, 3)] for u, v in edges: graph[u].append(v) graph[v].append(u) # omit for directed graph # Weighted graph weighted_graph = defaultdict(list) weighted_edges = [(0, 1, 4), (0, 2, 1), (1, 3, 1), (2, 3, 5)] for u, v, w in weighted_edges: weighted_graph[u].append((v, w)) weighted_graph[v].append((u, w)) # omit for directed graph ``` **Verify**: `len(graph[0])` → expected: `2` (node 0 connects to nodes 1 and 2) ### 2. Implement BFS for shortest path in unweighted graphs BFS explores nodes level by level using a FIFO queue. It naturally finds the shortest path (fewest edges) from the source to all reachable nodes. Time: O(V + E). [src2] ```python from collections import deque def bfs_shortest_path(graph, start, end): queue = deque([(start, [start])]) visited = {start} while queue: node, path = queue.popleft() if node == end: return path for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append((neighbor, path + [neighbor])) return None # no path exists ``` **Verify**: `bfs_shortest_path(graph, 0, 3)` → expected: `[0, 1, 3]` or `[0, 2, 3]` (both length 2) ### 3. Implement Dijkstra for weighted shortest paths Dijkstra's algorithm uses a min-heap (priority queue) to always process the node with the smallest known distance. It guarantees optimal shortest paths when all edge weights are non-negative. [src4] ```python import heapq def dijkstra(graph, start): dist = {start: 0} heap = [(0, start)] prev = {} while heap: d, u = heapq.heappop(heap) if d > dist.get(u, float('inf')): continue # stale entry for v, weight in graph[u]: new_dist = d + weight if new_dist < dist.get(v, float('inf')): dist[v] = new_dist prev[v] = u heapq.heappush(heap, (new_dist, v)) return dist, prev def reconstruct_path(prev, start, end): path = [] node = end while node != start: path.append(node) node = prev.get(node) if node is None: return None # no path path.append(start) return path[::-1] ``` **Verify**: `dijkstra(weighted_graph, 0)` → dist: `{0: 0, 1: 4, 2: 1, 3: 5}` ### 4. Implement DFS for traversal and cycle detection DFS explores as deep as possible before backtracking. The recursive version is cleaner, but the iterative version avoids stack overflow on deep graphs. For cycle detection in directed graphs, use three-color marking (white/gray/black). [src3] ```python def dfs_iterative(graph, start): visited = set() stack = [start] order = [] while stack: node = stack.pop() if node in visited: continue visited.add(node) order.append(node) for neighbor in reversed(graph[node]): # reverse for consistent order if neighbor not in visited: stack.append(neighbor) return order def has_cycle_directed(graph, num_nodes): WHITE, GRAY, BLACK = 0, 1, 2 color = [WHITE] * num_nodes def dfs(u): color[u] = GRAY for v in graph[u]: if color[v] == GRAY: return True # back edge = cycle if color[v] == WHITE and dfs(v): return True color[u] = BLACK return False return any(color[u] == WHITE and dfs(u) for u in range(num_nodes)) ``` **Verify**: `dfs_iterative(graph, 0)` → visits all reachable nodes from 0 ### 5. Implement Kruskal's MST with Union-Find Kruskal's algorithm sorts all edges by weight, then greedily adds each edge if it does not form a cycle (checked via Union-Find). Time: O(E log E). [src6] ```python class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, x, y): px, py = self.find(x), self.find(y) if px == py: return False if self.rank[px] < self.rank[py]: px, py = py, px self.parent[py] = px if self.rank[px] == self.rank[py]: self.rank[px] += 1 return True def kruskal(num_nodes, edges): # edges: list of (weight, u, v) edges.sort() uf = UnionFind(num_nodes) mst = [] total_weight = 0 for w, u, v in edges: if uf.union(u, v): mst.append((u, v, w)) total_weight += w if len(mst) == num_nodes - 1: break return mst, total_weight ``` **Verify**: MST of 4 nodes with edges `[(4,0,1),(1,0,2),(1,1,3),(5,2,3)]` → total weight: `3` ## Code Examples ### Python: Bellman-Ford with negative cycle detection ```python # Input: weighted directed graph as edge list, source vertex # Output: shortest distances dict, or raises ValueError on negative cycle def bellman_ford(num_nodes, edges, source): dist = [float('inf')] * num_nodes dist[source] = 0 prev = [None] * num_nodes # Relax all edges V-1 times for _ in range(num_nodes - 1): for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + w prev[v] = u # Check for negative-weight cycles for u, v, w in edges: if dist[u] + w < dist[v]: raise ValueError("Graph contains a negative-weight cycle") return dist, prev ``` ### JavaScript: BFS shortest path ```javascript // Input: adjacency list (Map), start node, end node // Output: shortest path array, or null if no path exists function bfsShortestPath(graph, start, end) { const queue = [[start, [start]]]; const visited = new Set([start]); while (queue.length > 0) { const [node, path] = queue.shift(); if (node === end) return path; for (const neighbor of (graph.get(node) || [])) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.push([neighbor, [...path, neighbor]]); } } } return null; } ``` ### Java: Dijkstra with priority queue ```java // Input: adjacency list (List>), source vertex, number of nodes // Output: int[] of shortest distances from source import java.util.*; public static int[] dijkstra(List> graph, int src, int n) { int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; // {distance, node} PriorityQueue pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); pq.offer(new int[]{0, src}); while (!pq.isEmpty()) { int[] curr = pq.poll(); int d = curr[0], u = curr[1]; if (d > dist[u]) continue; // stale entry for (int[] edge : graph.get(u)) { int v = edge[0], w = edge[1]; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.offer(new int[]{dist[v], v}); } } } return dist; } ``` ### Go: Topological sort (Kahn's algorithm) > Full script: [go-topological-sort-kahn-s-algorithm.go](scripts/go-topological-sort-kahn-s-algorithm.go) (32 lines) ```go // Input: number of nodes, adjacency list ([][]int) // Output: topological order slice, or error if cycle exists func topologicalSort(n int, graph [][]int) ([]int, error) { inDegree := make([]int, n) for u := 0; u < n; u++ { # ... (see full script) ``` ## Anti-Patterns ### Wrong: Using Dijkstra on graphs with negative edges ```python # BAD -- Dijkstra silently produces wrong results with negative weights # Graph: 0->1 (weight 4), 0->2 (weight 5), 2->1 (weight -3) # Dijkstra finds dist[1]=4 via direct edge, but actual shortest is 5+(-3)=2 graph = {0: [(1, 4), (2, 5)], 1: [], 2: [(1, -3)]} dist, _ = dijkstra(graph, 0) # Returns dist[1]=4, WRONG ``` ### Correct: Use Bellman-Ford for negative edges ```python # GOOD -- Bellman-Ford handles negative edges correctly edges = [(0, 1, 4), (0, 2, 5), (2, 1, -3)] dist, _ = bellman_ford(3, edges, 0) # Returns dist[1]=2, CORRECT ``` ### Wrong: Using DFS for shortest path in unweighted graphs ```python # BAD -- DFS does NOT guarantee shortest path # It may find a longer path first and return it def dfs_path(graph, start, end, visited=None): if visited is None: visited = set() visited.add(start) if start == end: return [start] for neighbor in graph[start]: if neighbor not in visited: path = dfs_path(graph, neighbor, end, visited) if path: return [start] + path return None # May return [0, 2, 3, 1] instead of [0, 1] on certain graphs ``` ### Correct: Use BFS for shortest path in unweighted graphs ```python # GOOD -- BFS guarantees shortest path (fewest edges) in unweighted graphs path = bfs_shortest_path(graph, 0, 1) # Always returns shortest path ``` ### Wrong: Using adjacency matrix for sparse graphs ```python # BAD -- O(V^2) space waste for sparse graphs # For V=100,000 nodes with 200,000 edges, this uses 40GB of memory adj_matrix = [[0] * V for _ in range(V)] # V^2 space # Neighbor iteration is O(V) per node instead of O(degree) ``` ### Correct: Use adjacency list for sparse graphs ```python # GOOD -- O(V + E) space, O(degree) neighbor iteration from collections import defaultdict adj_list = defaultdict(list) # Only stores actual edges for u, v in edges: adj_list[u].append(v) ``` ### Wrong: Forgetting to handle disconnected components ```python # BAD -- only traverses the component containing 'start' def bfs_all(graph, start): visited = set() queue = deque([start]) visited.add(start) while queue: node = queue.popleft() for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return visited # Misses disconnected nodes! ``` ### Correct: Iterate over all nodes to cover disconnected components ```python # GOOD -- handles disconnected graphs def bfs_all_components(graph, num_nodes): visited = set() components = [] for node in range(num_nodes): if node not in visited: component = set() queue = deque([node]) visited.add(node) while queue: u = queue.popleft() component.add(u) for v in graph[u]: if v not in visited: visited.add(v) queue.append(v) components.append(component) return components ``` ## Common Pitfalls - **Stale priority queue entries in Dijkstra**: When you update a distance, the old entry remains in the heap. Fix: always check `if d > dist[u]: continue` after popping. [src4] - **Stack overflow in recursive DFS on large graphs**: Python's default recursion limit is 1000. Fix: use iterative DFS with an explicit stack, or `sys.setrecursionlimit()` (risks segfault). [src3] - **Confusing undirected and directed edge insertion**: Adding `graph[u].append(v)` without `graph[v].append(u)` makes the graph directed. Fix: always clarify whether the graph is directed or undirected before building the adjacency list. [src5] - **Off-by-one in 0-indexed vs 1-indexed nodes**: Competitive programming often uses 1-indexed nodes while Python lists are 0-indexed. Fix: allocate arrays of size `n + 1` for 1-indexed problems, or normalize all inputs to 0-indexed. [src5] - **Not detecting negative cycles in Bellman-Ford**: Running only V-1 relaxation passes finds shortest paths but does not flag negative cycles. Fix: run one more pass — if any distance decreases, a negative cycle exists. [src8] - **Using Prim's algorithm on disconnected graphs**: Prim's finds an MST for a single connected component. Fix: check connectivity first, or run Prim's from each component separately to find a minimum spanning forest. [src6] - **Forgetting visited set in BFS/DFS**: Without marking nodes as visited, algorithms revisit nodes and may loop infinitely on cyclic graphs. Fix: always mark a node as visited when it is first discovered (enqueued/pushed), not when processed. [src2] ## Version History & Compatibility N/A — These are timeless computer science algorithms. BFS and DFS date to the 1950s-1960s, Dijkstra to 1956, Bellman-Ford to 1958, Floyd-Warshall to 1962, Kruskal to 1956, Prim to 1957, Tarjan SCC to 1972, and A* to 1968. The algorithms are language-agnostic and implementation-stable. ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Finding shortest path in unweighted graph | Graph has weighted edges | Dijkstra or Bellman-Ford | | Finding shortest path with non-negative weights | Graph has negative edge weights | Bellman-Ford | | Need heuristic speedup to single target | No good heuristic available, or need all-pairs | Dijkstra (no heuristic) or Floyd-Warshall | | Need all-pairs shortest paths in small dense graph | Graph has > ~5,000 nodes | Run Dijkstra from each source | | Need MST of sparse graph | Graph is very dense (E ~ V^2) | Prim with Fibonacci heap | | Need topological ordering of tasks | Graph contains cycles | Detect cycles first; topological sort impossible | | Need to find all SCCs in directed graph | Graph is undirected | Use DFS/BFS connected components instead | | Need cycle detection in directed graph | Graph is undirected | DFS with parent tracking or Union-Find | ## Important Caveats - Real-world graph libraries (NetworkX, JGraphT, Boost.Graph) are heavily optimized and preferred over hand-rolled implementations for production use; use custom implementations mainly for competitive programming, interviews, or when library overhead is unacceptable. - A* performance depends entirely on heuristic quality: a perfect heuristic makes it optimal in O(shortest path length), while a zero heuristic degrades it to Dijkstra; Manhattan distance works for grids, Euclidean distance for geometric graphs. - Parallel/distributed graph algorithms (e.g., Pregel, GraphX) behave differently from sequential versions and require separate study for large-scale graph processing. - Priority queue implementation matters significantly: Fibonacci heap gives the best theoretical Dijkstra complexity O(E + V log V) but has high constant factors; binary heap O((V+E) log V) is faster in practice for most graphs. ## Related Units - [Topological Sort](/software/patterns/topological-sort/2026) - [Dynamic Programming Patterns](/software/patterns/dynamic-programming/2026) - [Sorting Algorithms](/software/patterns/sorting-algorithms/2026) - [Union-Find / Disjoint Set](/software/patterns/union-find-disjoint-set/2026)