Graph Algorithms Beyond Traversal

Why this module exists

BFS/DFS is table stakes. Real graph interviews often need MSTs, SCCs, and bipartite matching. These are foundational for networking, compilers, and scheduling.

Minimum Spanning Tree (MST)

For a connected, weighted, undirected graph, an MST connects all nodes with minimum total weight.

Two standard algorithms:

• Kruskal: sort edges, union if they connect two components
• Prim: grow a tree using a min-heap over edges

Kruskal is great when you already have edges; Prim is natural for dense graphs.

Strongly Connected Components (SCC)

In a directed graph, an SCC is a maximal set of nodes where each reaches every other.

Kosaraju (2-pass):

1. DFS on original graph to get finish order
2. DFS on reversed graph in that order

Tarjan does it in one pass using low-link values.

Bipartite Matching

A bipartite graph has left and right partitions. A matching is a set of edges with no shared endpoints.

Key idea: augmenting paths. Each augment increases matching size by 1.

Hopcroft-Karp uses BFS + DFS layers for O(E sqrt V).

What you will build

• MST total weight with Kruskal.
• Count SCCs with Kosaraju.
• Maximum bipartite matching.