Graph Algorithms

Network Flow

Max-flow finds the most that can travel from a source to a sink through capacitated edges; by the max-flow min-cut theorem, that same number is also the cheapest set of edges whose removal would disconnect them.

Each edge has a capacity; flow through it can't exceed that capacity, and flow into a vertex must equal flow out (except source/sink)
Ford-Fulkerson: repeatedly find an augmenting path from source to sink in the residual graph, push flow equal to its bottleneck capacity
Edmonds-Karp: Ford-Fulkerson using BFS to find the augmenting path each time — guarantees O(VE²), avoiding pathological slow convergence
Max-flow min-cut theorem: the maximum flow value equals the capacity of the minimum cut separating source from sink
Models far beyond literal "flow": bipartite matching, project selection, image segmentation all reduce to max-flow — see Reductions And Intractability

Edmonds-Karp (Ford-Fulkerson with BFS augmenting paths)

static int maxFlow(int[][] capacity, int source, int sink) {
    int n = capacity.length;
    int[][] residual = deepCopy(capacity);
    int total = 0;
    int[] parent = new int[n];
    while (bfsFindPath(residual, source, sink, parent)) {
        int bottleneck = Integer.MAX_VALUE;
        for (int v = sink; v != source; v = parent[v]) {
            bottleneck = Math.min(bottleneck, residual[parent[v]][v]);
        }
        for (int v = sink; v != source; v = parent[v]) {
            residual[parent[v]][v] -= bottleneck;
            residual[v][parent[v]] += bottleneck;   // open up the reverse edge
        }
        total += bottleneck;
    }
    return total;
}

Problems that reduce to max-flow
Problem	Reduction
Bipartite matching	source → left vertices → right vertices → sink, unit capacities
Project/task selection with dependencies	min-cut over a project-profit graph
Edge/vertex connectivity	min-cut capacity equals the number of edge-disjoint paths (Menger's theorem)