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).
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “How does Tarjan's algorithm find strongly connected components in O(V+E)?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Tarjan's SCC algorithm performs a single DFS and maintains two values per node: disc[v] (the DFS discovery timestamp) and low[v] (the minimum discovery timestamp reachable from v's subtree via at most one back edge). A node v is the root of an SCC when low[v] == disc[v] — meaning no node in v's subtree can reach any ancestor of v. The algorithm uses an explicit stack to collect nodes in the current DFS path. When the SCC root condition is detected, pop nodes from the stack until v is popped — these form one SCC. The O(V+E) complexity comes from visiting each node and edge exactly once in the DFS. Key distinction from BFS/DFS: the low-link value propagation (low[u] = min(low[u], low[v]) when returning from a child) is what enables SCC detection in a single pass, rather than Kosaraju's two-pass approach.” }
},
{
“@type”: “Question”,
“name”: “What is the difference between a bridge and an articulation point?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “A bridge (cut edge) is an edge whose removal disconnects the graph — removing it increases the number of connected components. An articulation point (cut vertex) is a node whose removal disconnects the graph — removing it splits the graph into two or more components. They are related but distinct: a bridge's two endpoints are not necessarily articulation points (if each endpoint connects to other edges), but a node incident to a bridge is an articulation point only if it has degree > 1 or is an internal network junction. Detection algorithm: both use DFS with low-link values. Bridge condition: for edge (u,v) where v is a child of u in DFS tree, if low[v] > disc[u], then (u,v) is a bridge — the subtree rooted at v cannot reach u or any ancestor of u. Articulation point condition: (1) u is the DFS root and has 2+ DFS tree children, or (2) u is not root and low[v] >= disc[u] for some child v. Interview application: find single points of failure in a network topology.” }
},
{
“@type”: “Question”,
“name”: “When should you use Dijkstra vs Bellman-Ford vs BFS for shortest paths?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “BFS: use when all edge weights are equal (or the graph is unweighted). Time O(V+E). BFS is the fastest option for unweighted graphs — it naturally finds shortest paths by exploring level by level. Dijkstra: use for weighted graphs with non-negative edge weights. Time O((V+E) log V) with a binary heap. This is the standard algorithm for road networks, GPS routing, and network routing. Never use Dijkstra with negative edges — it will produce incorrect results because it assumes relaxing a node never improves later. Bellman-Ford: use when the graph may have negative edge weights. Time O(V*E). Also detects negative cycles (if after V-1 relaxations an edge can still be relaxed, a negative cycle exists). Slower than Dijkstra but handles negative weights. Floyd-Warshall: use for all-pairs shortest paths in dense graphs. Time O(V^3), Space O(V^2). Practical when V <= 500 and you need distances between all pairs of nodes.” }
}
]
}