MST, strongly connected components, bridges, and advanced shortest path algorithms.
Advanced graph algorithms tackle minimum spanning trees, strongly connected components, bridges, and articulation points. These appear in system design contexts and senior-level interviews.
MST O(E log E) · SCC O(V+E)
O(V+E)
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
Minimum Spanning Tree: Kruskal (sort edges + union-find) or Prim (greedy + heap)
sort edges by weight, add if it does not create a cycle
greedily add the cheapest edge connecting visited and unvisited nodes
Strongly Connected Components: Kosaraju or Tarjan O(V+E)
edges whose removal disconnects graph; Tarjan's bridge finding
vertices whose removal disconnects graph