Graph Theory37 sections · 1633 units
Open in Course

Algorithm - Find Min Cut

(Step by step)

1.1. Compute max flow from ss to tt using any max flow algorithm (Dinic, Ford-Fulkerson, etc.).

2.2. Build the residual graph after max flow. Include edges with remaining capacity.

3.3. Run BFS/DFS from ss in the residual graph to mark all reachable vertices as SS.

4.4. All other vertices form TT. These are unreachable from ss.

5.5. Edges from SS to TT in the original graph form the minimum cut.