Graph Algorithm Selection Guide
Choosing the right graph algorithm is the first step in any graph interview question. BFS: unweighted shortest path, level-order traversal, connected components. DFS: cycle detection, topological sort, SCC, path enumeration. Dijkstra: single-source shortest path with non-negative weights. Bellman-Ford: shortest path with negative weights, detects negative cycles. Floyd-Warshall: all-pairs shortest paths, O(V^3). Prim/Kruskal: minimum spanning tree. Topological sort: dependency ordering in a DAG. Tarjan/Kosaraju: strongly connected components. The key: if edge weights are all equal (or unweighted), BFS is sufficient and faster. Only use Dijkstra when weights differ.
Dijkstra’s Algorithm: O((V + E) log V)
Single-source shortest path for non-negative weights. Use a min-heap (priority queue). Start: add (0, source) to heap. On each pop: if distance is outdated (already found a shorter path), skip. Otherwise: for each neighbor, compute tentative distance; if shorter than known, update and push to heap.
import heapq
def dijkstra(graph, src, n):
# graph[u] = [(weight, v), ...]
dist = [float('inf')] * n
dist[src] = 0
heap = [(0, src)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]: # stale entry
continue
for w, v in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(heap, (dist[v], v))
return distWhy skip stale entries: the heap may contain outdated (larger) distances for a node. When we pop a stale entry, the node has already been settled at a shorter distance — skip it. This is correct because Dijkstra’s guarantee: the first time a node is popped from the heap, it has its final shortest distance. Key applications: LC 743 (Network Delay Time), LC 1631 (Minimum Effort Path — use Dijkstra with edge weight = max height difference), LC 778 (Swim in Rising Water — binary search + BFS, or Dijkstra).
Bellman-Ford: Negative Weights and Cycle Detection
Relaxes all edges V-1 times. After V-1 rounds, all shortest paths are found (a shortest path has at most V-1 edges if no negative cycle). Run one more round: if any distance still decreases, a negative cycle is reachable. O(VE) time. Use when: edge weights can be negative, or you need to detect negative cycles.
def bellman_ford(n, edges, src):
# edges = [(u, v, w), ...]
dist = [float('inf')] * n
dist[src] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative cycles
for u, v, w in edges:
if dist[u] + w < dist[v]:
return None # negative cycle
return distTopological Sort: Kahn’s Algorithm
Topological order of a DAG: process nodes in the order such that all dependencies come before dependents. Kahn’s BFS: compute in-degrees; add all 0-in-degree nodes to queue; repeatedly remove a node, decrement neighbors’ in-degrees, add newly 0-in-degree nodes. If all nodes are processed: valid topological order. If not: cycle exists.
from collections import deque
def topo_sort(n, prerequisites):
adj = [[] for _ in range(n)]
in_degree = [0] * n
for a, b in prerequisites:
adj[b].append(a)
in_degree[a] += 1
q = deque(i for i in range(n) if in_degree[i] == 0)
order = []
while q:
node = q.popleft()
order.append(node)
for nei in adj[node]:
in_degree[nei] -= 1
if in_degree[nei] == 0:
q.append(nei)
return order if len(order) == n else [] # empty = cycleStrongly Connected Components: Kosaraju’s Algorithm
An SCC is a maximal set of nodes where every node is reachable from every other. Applications: finding circular dependencies, condensation graph (DAG of SCCs). Kosaraju’s two-pass DFS: (1) DFS on original graph, push nodes to stack in finish-time order. (2) Transpose the graph (reverse all edges). (3) DFS on transposed graph in reverse finish-time order (pop from stack). Each DFS tree in pass 2 is one SCC.
def kosaraju(n, edges):
adj = [[] for _ in range(n)]
radj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
radj[v].append(u)
visited = [False] * n
order = []
def dfs1(u):
visited[u] = True
for v in adj[u]:
if not visited[v]: dfs1(v)
order.append(u)
for i in range(n):
if not visited[i]: dfs1(i)
visited = [False] * n
sccs = []
def dfs2(u, comp):
visited[u] = True
comp.append(u)
for v in radj[u]:
if not visited[v]: dfs2(v, comp)
while order:
u = order.pop()
if not visited[u]:
comp = []
dfs2(u, comp)
sccs.append(comp)
return sccsSee also: Meta Interview Prep
See also: Atlassian Interview Prep
See also: Databricks Interview Prep