Advanced Graph Algorithms for Interviews
Beyond BFS/DFS and basic shortest paths, interviews at senior levels test Tarjan’s algorithm for SCCs, articulation points, Dijkstra with priority queues, and minimum spanning trees. These appear in network design, dependency resolution, and reliability engineering problems.
Strongly Connected Components (Tarjan’s Algorithm)
An SCC is a maximal set of nodes where every node is reachable from every other. Tarjan finds all SCCs in one O(V+E) DFS pass.
def tarjan_scc(graph):
n = len(graph)
index_counter = [0]
index = {} # discovery time
lowlink = {} # minimum reachable discovery time
on_stack = {}
stack = []
sccs = []
def strongconnect(v):
index[v] = lowlink[v] = index_counter[0]
index_counter[0] += 1
stack.append(v)
on_stack[v] = True
for w in graph[v]:
if w not in index:
strongconnect(w)
lowlink[v] = min(lowlink[v], lowlink[w])
elif on_stack[w]:
lowlink[v] = min(lowlink[v], index[w])
if lowlink[v] == index[v]: # v is root of an SCC
scc = []
while True:
w = stack.pop()
on_stack[w] = False
scc.append(w)
if w == v: break
sccs.append(scc)
for v in range(n):
if v not in index:
strongconnect(v)
return sccs
Key insight: lowlink[v] = min discovery time reachable from v’s subtree via back edges. When lowlink[v] == index[v], v is the root of an SCC — pop everything above v from the stack.
Articulation Points and Bridges
An articulation point (cut vertex) is a node whose removal disconnects the graph. A bridge is an edge whose removal disconnects the graph. Both found via one O(V+E) DFS.
def find_bridges(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
disc = [-1] * n
low = [-1] * n
timer = [0]
bridges = []
def dfs(u, parent):
disc[u] = low[u] = timer[0]
timer[0] += 1
for v in graph[u]:
if disc[v] == -1:
dfs(v, u)
low[u] = min(low[u], low[v])
if low[v] > disc[u]: # v cannot reach u's ancestors
bridges.append((u, v))
elif v != parent:
low[u] = min(low[u], disc[v])
for i in range(n):
if disc[i] == -1:
dfs(i, -1)
return bridges
Bridge condition: low[v] > disc[u] — the subtree rooted at v has no back edge reaching u or u’s ancestors. Articulation point condition: (1) u is root and has 2+ children in DFS tree, or (2) u is not root and low[v] >= disc[u] for some child v.
Dijkstra’s Algorithm
import heapq
def dijkstra(graph, src):
dist = {node: float('inf') for node in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]: continue # stale entry
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
heapq.heappush(pq, (dist[v], v))
return dist
Time: O((V+E) log V). The “if d > dist[u]: continue” check is critical — it skips stale priority queue entries without a decrease-key operation.
Minimum Spanning Tree (Kruskal’s)
def kruskal(n, edges):
edges.sort(key=lambda e: e[2]) # sort by weight
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
def union(x, y):
px, py = find(x), find(y)
if px == py: return False
parent[px] = py
return True
mst_cost = 0
mst_edges = []
for u, v, w in edges:
if union(u, v):
mst_cost += w
mst_edges.append((u, v, w))
return mst_cost, mst_edges
Interview Applications
- SCC: detect circular dependencies in package managers, find groups of mutually reachable web pages, identify deadlock cycles.
- Bridges/articulation points: find single points of failure in a network, identify critical roads in a city graph.
- Dijkstra: GPS routing, network routing protocols (OSPF), word ladder shortest transformation.
- MST: minimum cost to connect all cities, cluster analysis (remove heaviest MST edges), approximation for TSP.
Interview Tips
- SCC → Tarjan or Kosaraju (two-pass DFS). Tarjan is one pass, preferred in interviews.
- Bridges → DFS with low-link values. Same framework as Tarjan.
- Dijkstra fails with negative weights — use Bellman-Ford instead.
- For dense graphs (E ≈ V^2), Prim’s MST with adjacency matrix is O(V^2), better than Kruskal’s O(E log E).