DSA: Graphs Advanced Algorithms
Explore SCCs, Eulerian paths, max flow, bipartite matching, and other advanced graph techniques.
Strongly Connected Components (Kosaraju's Algorithm)
A Strongly Connected Component (SCC) is a maximal set of vertices in a directed graph where every vertex is reachable from every other vertex. Kosaraju's algorithm finds all SCCs in O(V + E).
Kosaraju's Algorithm
Two-pass DFS: first on the original graph to record finish order, then on the reversed graph.
- Pass 1: DFS on original graph, push each node onto a stack when finished
- Reverse: transpose all edges in the graph
- Pass 2: pop nodes from stack, run DFS on reversed graph; each DFS tree = one SCC
- Time complexity: O(V + E), space: O(V + E)
Kosaraju's SCC
C++Find all strongly connected components using two DFS passes.
Eulerian Path and Circuit
An Eulerian path visits every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.
Eulerian Path / Circuit
Existence depends on vertex degrees. Hierholzer's algorithm finds the path/circuit in O(E).
- Circuit exists: graph connected + all vertices have even degree
- Path exists: graph connected + exactly 2 vertices have odd degree (start and end)
- Hierholzer's algorithm: follow edges greedily, splice in sub-circuits
- Different from Hamiltonian path: Eulerian covers edges, Hamiltonian covers vertices
Eulerian Path/Circuit Check
C++Check degree conditions to determine Eulerian path or circuit existence.
Hamiltonian Cycle (Backtracking)
A Hamiltonian cycle visits every vertex exactly once and returns to the starting vertex. No polynomial-time algorithm is known; backtracking is the standard exact approach.
Hamiltonian Cycle
NP-complete problem. Backtracking explores all vertex orderings, pruning dead ends early.
- Try adding each unvisited adjacent vertex to the current path
- Prune: if no edge exists to the next candidate, backtrack
- Base case: all V vertices visited and edge back to start exists
- Worst case: O(V!), only feasible for small graphs
Hamiltonian Cycle
C++Backtracking search for a cycle that visits every vertex exactly once.
Maximum Flow (Ford-Fulkerson / Edmonds-Karp)
Maximum flow finds the greatest amount of flow that can be sent from a source to a sink in a capacity-constrained network. Edmonds-Karp uses BFS to find augmenting paths, giving O(V * E²).
Ford-Fulkerson / Edmonds-Karp
Augment flow along source-to-sink paths repeatedly until no augmenting path remains.
- Residual graph: tracks remaining capacity on each edge (forward and backward)
- Augmenting path: path from source to sink with positive residual capacity
- Each iteration: find path via BFS (Edmonds-Karp), push bottleneck flow
- Termination: no augmenting path in residual graph means max flow reached
- Max-Flow Min-Cut theorem: max flow = capacity of minimum cut
Edmonds-Karp Max Flow
C++BFS-based augmenting path search for maximum flow in a network.
Minimum Cut
After running max flow, the minimum cut can be found by identifying which vertices are reachable from the source in the residual graph. Edges crossing from reachable to non-reachable form the min cut.
Min Cut
Vertices reachable from source in residual graph form set S; remaining form set T. Cut edges go S to T.
- Run max flow algorithm first to saturate the network
- BFS/DFS on residual graph from source to find reachable set S
- Min cut edges: original edges from S to T (not in S) with full capacity used
- Min cut capacity = max flow value (by Max-Flow Min-Cut theorem)
Min Cut Detection
C++Find minimum cut edges after running max flow.
Maximum Bipartite Matching
In a bipartite graph, vertices split into two disjoint sets with edges only between sets. Maximum bipartite matching finds the largest set of edges with no shared vertices (using the Hungarian/augmenting path approach).
Bipartite Matching
Augment the matching greedily using DFS to find alternating paths from unmatched left vertices.
- Alternating path: alternates between unmatched and matched edges
- Augmenting path: alternating path starting and ending at unmatched vertices
- Flip matched/unmatched along augmenting path to increase matching by 1
- Time complexity: O(V * E) using DFS augmentation
- Equivalent to max flow with unit capacities on a constructed flow network
Maximum Bipartite Matching
C++DFS augmenting path approach for maximum matching in bipartite graphs.
Algorithm Comparison
Quick reference for advanced graph algorithms covered on this page.
| Algorithm | Problem Solved | Time Complexity | Key Technique |
|---|---|---|---|
| Kosaraju's | Strongly Connected Components | O(V + E) | Two-pass DFS + reverse graph |
| Tarjan's | Strongly Connected Components | O(V + E) | Single DFS with low-link values |
| Hierholzer's | Eulerian path / circuit | O(E) | Greedy edge traversal + splice |
| Hamiltonian (backtrack) | Hamiltonian cycle | O(V!) | Backtracking with pruning |
| Edmonds-Karp | Max flow | O(V * E²) | BFS augmenting paths |
| Min Cut | Minimum cut | O(V + E) post-flow | Reachable set in residual graph |
| Bipartite Matching | Maximum matching | O(V * E) | DFS augmenting paths |
Knowledge Check
1. What does a Strongly Connected Component (SCC) represent in a directed graph?
2. What is the first step in Kosaraju's algorithm?
3. An Eulerian circuit exists in an undirected graph when:
4. What distinguishes an Eulerian path from an Eulerian circuit?
5. What is the time complexity of the Ford-Fulkerson algorithm with BFS (Edmonds-Karp)?
6. The Max-Flow Min-Cut theorem states:
7. In bipartite matching, what does an augmenting path represent?
8. The Hamiltonian cycle problem is: