Advanced Graphs: Components, Bridges, Matching and Max-Flow

#Four Questions About Connection

You know breadth-first search (BFS) and depth-first search (DFS) from the Graphs lesson, and Dijkstra from the Shortest Paths lesson. Those answer "how far". This lesson answers "how connected" and "how much".

Here are the questions. In a directed graph, which groups of vertices can all reach each other? In an undirected graph, which single edge or vertex, if removed, splits the graph? Can the vertices be split into two sides with every edge crossing between the sides? And on a network with pipe sizes, how much can flow from a source to a sink?

#Strongly Connected Components

Think of one-way streets. Inside an SCC you can drive from any junction to any other and back. Between SCCs you only go one way.

Two facts make SCCs useful. First, every vertex belongs to exactly one SCC, because strong connection is symmetric and transitive, so the components split the vertices cleanly. A vertex alone is a component of size one.

Our example graph has seven vertices and eight arrows.

A->B   B->C   C->A   B->D
D->E   E->F   F->D   F->G

A, B and C form a loop, so they are one SCC. D, E and F form another. G is alone. The arrow B to D and the arrow F to G go from one component to the next, never back.

#Kosaraju: Why It Works and the Code

Why does flipping help? Flipping arrows never changes which vertices are strongly connected, because a path both ways stays a path both ways. But it changes which components can leak into others.

Here is the key fact. If an arrow leads from component X to component Y, then the latest finisher in X finishes after every vertex in Y. If DFS enters X first, it reaches all of Y before it can finish its start vertex. If DFS enters Y first, it cannot reach X at all, because the condensation is a DAG, so Y finishes completely before X starts.

So the vertex with the latest finish time sits in a component with no arrows coming in. In the reversed graph that component has no arrows going out. A DFS from it visits exactly that one component and nothing more. Mark those vertices as seen and repeat. The next latest unseen finisher is in a component whose only outside neighbors, in the reversed graph, are already marked.

Trace it on the example. The first pass starts at A and goes A, B, C. C's only arrow goes back to A, so C finishes first. Back at B, the arrow to D leads on to E, F, then F's arrows go to D (seen) and G. G finishes, then F, E, D, B and A.

Now the code. It uses an explicit stack, because Python stops a recursive function at about 1,000 nested calls and a long chain of vertices would crash it. Each stack entry holds a vertex and an iterator over its neighbors. When the iterator runs out, the vertex finishes.

edges = [("A", "B"), ("B", "C"), ("C", "A"), ("B", "D"),
         ("D", "E"), ("E", "F"), ("F", "D"), ("F", "G")]
graph = {}
for u, v in edges:
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, [])


def reverse(graph):
    """Flip every arrow. O(V + E) time and space."""
    rev = {u: [] for u in graph}
    for u in graph:
        for v in graph[u]:
            rev[v].append(u)
    return rev


def dfs_finish(graph, starts, seen):
    """Iterative DFS from each start not yet seen. Returns vertices in finishing order."""
    finished = []
    for s in starts:
        if s in seen:
            continue
        seen.add(s)
        stack = [(s, iter(graph[s]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if v not in seen:
                    seen.add(v)
                    stack.append((v, iter(graph[v])))
                    break
            else:                        # every neighbor done, so u finishes
                finished.append(u)
                stack.pop()
    return finished


def kosaraju(graph):
    """Strongly connected components. O(V + E) time, O(V + E) space."""
    first = dfs_finish(graph, list(graph), set())
    rev = reverse(graph)
    seen, comps = set(), []
    for s in reversed(first):            # latest finisher first
        if s not in seen:
            comps.append(sorted(dfs_finish(rev, [s], seen)))
    return comps


print(dfs_finish(graph, list(graph), set()))
print(kosaraju(graph))
# Output:
# ['C', 'G', 'F', 'E', 'D', 'B', 'A']
# [['A', 'B', 'C'], ['D', 'E', 'F'], ['G']]

The first line matches the table. The cost is O(V + E) time: two full DFS passes plus one pass to flip the arrows, and each vertex and arrow is touched a constant number of times. The extra space is O(V + E) for the reversed copy and the stack.

Tarjan's algorithm finds the same components in one DFS pass using the low-links of the next section, with the same O(V + E) time and no reversed copy. Kosaraju is easier to prove, so it comes first.

#Bridges and Articulation Points

The naive way removes each edge and re-runs BFS. That costs O(E) per edge, so O(E²) in total. One DFS can do it in O(V + E).

Take eight edges: a triangle on 0, 1, 2, a link 2 to 3, a triangle on 3, 4, 5, and a pendant edge 5 to 6. Here are the arrays after DFS from vertex 0.

def bridges_and_cuts(n, edges):
    """Bridges and articulation points of an undirected graph on vertices 0..n-1.

    One DFS: O(V + E) time, O(V + E) space. Recursive, so depth up to V.
    """
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    tin = [-1] * n          # discovery time
    low = [0] * n           # earliest discovery time reachable
    bridges, cuts, clock = [], set(), [0]

    def dfs(u, parent_edge):
        tin[u] = low[u] = clock[0]
        clock[0] += 1
        children = 0
        for v, i in adj[u]:
            if i == parent_edge:
                continue                       # do not walk back along the same edge
            if tin[v] != -1:
                low[u] = min(low[u], tin[v])   # back edge
            else:
                dfs(v, i)
                children += 1
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    bridges.append(edges[i])
                if parent_edge != -1 and low[v] >= tin[u]:
                    cuts.add(u)
        if parent_edge == -1 and children > 1:
            cuts.add(u)

    for s in range(n):
        if tin[s] == -1:
            dfs(s, -1)
    return sorted(bridges), sorted(cuts), tin, low


edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (5, 6)]
b, c, tin, low = bridges_and_cuts(7, edges)
print(b)
print(c)
print(tin)
print(low)
# Output:
# [(2, 3), (5, 6)]
# [2, 3, 5]
# [0, 1, 2, 3, 4, 5, 6]
# [0, 0, 0, 3, 3, 3, 6]

Notice that the code skips the parent by edge number, not by vertex. Two parallel edges between the same pair are a real second route, so neither is a bridge. Skipping by vertex would call both of them bridges.

The cost is O(V + E) time, because each edge is looked at twice, once from each end. The space is O(V + E) for the adjacency lists, plus recursion depth up to V. For a path of tens of thousands of vertices, rewrite the DFS with an explicit stack as in the Kosaraju code.

#Bipartite Graphs and the Two-Color Test

The test is a two-coloring. Color the start vertex 0. Every neighbor must be color 1. Every neighbor of those must be 0, and so on. If an edge ever joins two vertices of the same color, the graph is not bipartite. BFS does this in one pass.

from collections import deque


def two_color(graph):
    """Return (True, colors) or (False, (u, v)) where u and v share a color across an edge.

    BFS over every component: O(V + E) time, O(V) space."""
    color = {}
    for s in graph:
        if s in color:
            continue
        color[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:
                    return False, (u, v)
    return True, color


def undirected(pairs):
    g = {}
    for u, v in pairs:
        g.setdefault(u, []).append(v)
        g.setdefault(v, []).append(u)
    return g


print(two_color(undirected([("a", "b"), ("b", "c"), ("c", "d"), ("d", "a")])))
print(two_color(undirected([("a", "b"), ("b", "c"), ("c", "a")])))
print(two_color(undirected([(i, (i + 1) % 5) for i in range(5)])))
print(two_color({}))
# Output:
# (True, {'a': 0, 'b': 1, 'd': 1, 'c': 0})
# (False, ('b', 'c'))
# (False, (2, 3))
# (True, {})

The cost is O(V + E) time, because each vertex enters the queue once and each edge is checked twice. The space is O(V) for the colors and the queue.

Going one way, any cycle in a bipartite graph alternates sides, so it must return after an even number of steps. Going the other way, suppose BFS finds an edge joining two vertices of the same color. Both sit at levels of the same parity, and the two BFS paths back to their meeting point, plus that edge, form a cycle of odd length. So the failing edge is a witness, and the code returns it.

The outer loop over every start vertex matters. A graph can have several pieces, and each piece is colored on its own.

#Matching: Augmenting Paths

A greedy approach takes any free pair and moves on, and it can get stuck. Say person 0 can do jobs 0 or 1, and person 1 can do only job 0. If person 0 grabs job 0, person 1 has nothing, though giving person 0 job 1 would match both.

Here is the small case by hand.

def max_matching(left_adj, n_right):
    """Kuhn's algorithm. left_adj[u] lists the right vertices u may take.

    Returns (size, match_right, steps). O(V * E) time, O(V) space."""
    match_right = [-1] * n_right
    steps = [0]

    def try_assign(u, seen):
        for r in left_adj[u]:
            steps[0] += 1
            if r in seen:
                continue
            seen.add(r)
            if match_right[r] == -1 or try_assign(match_right[r], seen):
                match_right[r] = u
                return True
        return False

    size = 0
    for u in range(len(left_adj)):
        if try_assign(u, set()):
            size += 1
    return size, match_right, steps[0]


print(max_matching([[0, 1], [0]], 2))
print(max_matching([[0, 1], [0], [1, 2], [2, 3]], 4))
print(max_matching([[0], [0], [0]], 1))
print(max_matching([], 0))
# Output:
# (2, [1, 0], 4)
# (4, [1, 0, 2, 3], 16)
# (1, [0], 5)
# (0, [], 0)

#Max-Flow: The Residual Graph

Here is a diamond network. S has edges to A and B of capacity 1, A has an edge to B of capacity 1, and A and B each have an edge to T of capacity 1.

Suppose you pick paths badly. Push one unit along S, A, B, T first. Now S to A is full, A to B is full and B to T is full. Greedy has no path left and stops at 1, but the answer is 2. The mistake was a path choice you could not undo.

After the bad first path, B to A has residual room 1. Now S, B, A, T is a valid path: it uses the new route S to B, cancels the unit on A to B, and finishes on A to T. The total becomes 2.

That bound can be terrible. Take capacities of 1,000,000 on four edges and a middle edge of capacity 1 between the two sides. A DFS that keeps choosing the middle edge, then its undo, then the middle again, adds 1 per round and needs 2,000,000 rounds.

The reason, in words: the BFS distance from s to any vertex in the residual graph never decreases, and each augmentation saturates at least one edge on a shortest path, which can happen to a given edge only about V/2 times. Each BFS costs O(E), so the total is O(V·E²) time and O(V + E) space.

from collections import deque


def edmonds_karp(n, edges, s, t):
    """Max flow. edges are (u, v, capacity). Returns (flow, augmentations, scans).

    Each augmentation is one BFS, O(E). At most V*E/2 augmentations, so O(V * E^2) time.
    Space O(V + E): every edge gets a partner edge with capacity 0 to carry the undo."""
    to, cap, adj = [], [], [[] for _ in range(n)]
    for u, v, c in edges:
        adj[u].append(len(to)); to.append(v); cap.append(c)      # forward edge, even index
        adj[v].append(len(to)); to.append(u); cap.append(0)      # reverse edge, odd index
    flow = augmentations = scans = 0
    while True:
        parent_edge = [-1] * n
        parent_edge[s] = -2
        queue = deque([s])
        while queue and parent_edge[t] == -1:
            u = queue.popleft()
            for e in adj[u]:
                scans += 1
                if cap[e] > 0 and parent_edge[to[e]] == -1:
                    parent_edge[to[e]] = e
                    queue.append(to[e])
        if parent_edge[t] == -1:
            return flow, augmentations, scans
        push, v = float("inf"), t                 # bottleneck along the path
        while v != s:
            e = parent_edge[v]
            push = min(push, cap[e])
            v = to[e ^ 1]
        v = t
        while v != s:
            e = parent_edge[v]
            cap[e] -= push
            cap[e ^ 1] += push
            v = to[e ^ 1]
        flow += push
        augmentations += 1


# S=0 A=1 B=2 C=3 D=4 T=5
net = [(0, 1, 10), (0, 2, 10), (1, 2, 2), (1, 3, 4), (1, 4, 8),
       (2, 4, 9), (3, 5, 10), (4, 3, 6), (4, 5, 10)]
print(edmonds_karp(6, net, 0, 5))
diamond = [(0, 1, 1), (0, 2, 1), (1, 2, 1), (1, 3, 1), (2, 3, 1)]
print(edmonds_karp(4, diamond, 0, 3))
big = 10**6
cross = [(0, 1, big), (0, 2, big), (1, 2, 1), (1, 3, big), (2, 3, big)]
print(edmonds_karp(4, cross, 0, 3))
print(edmonds_karp(2, [], 0, 1))
# Output:
# (19, 4, 55)
# (2, 2, 12)
# (2000000, 2, 12)
# (0, 0, 0)

The worked network has six vertices S, A, B, C, D and T with nine edges. Its four BFS augmentations are shown here, in the order the code finds them.

After round 4, BFS from S finds no path to T, so the answer is 19. The cross network with capacities of a million finishes in 2 rounds, because BFS prefers the two-edge paths and never touches the capacity-1 middle edge.

#Max-Flow Min-Cut and Matching as Flow

When no augmenting path remains, let the s side be every vertex still reachable from s in the residual graph. Every edge leaving that side must be full, or its far end would be reachable. Every edge entering that side must carry zero, or its undo edge would reach out. So the flow equals the capacity of that cut. Since no flow beats any cut, both are optimal.

In the worked network, the vertices reachable from S after the last round are S and B. The edges leaving that side are S to A with capacity 10 and B to D with capacity 9. The cut costs 19, the same as the flow. To cut the network cheaply, remove exactly those two pipes.

Matching is a flow problem too. Add a source with an edge of capacity 1 to each person, an edge of capacity 1 from each job to a new sink, and keep person-to-job edges at capacity 1. Whole-number flows then correspond to matchings, and the max-flow value is the maximum matching. Kuhn's algorithm is Ford-Fulkerson on this graph, with each augmenting path found by DFS.

For bipartite graphs, König's theorem adds that the maximum matching equals the smallest set of vertices that touches every edge.

#Eulerian Paths and Graph Coloring

Two more graph questions look like the ones above and are easy to confuse with harder ones.

def euler_status(graph):
    """Connected undirected graph: 'circuit', 'path' or 'none'. O(V) after degrees are known."""
    odd = sum(1 for u in graph if len(graph[u]) % 2)
    return {0: "circuit", 2: "path"}.get(odd, "none")


square = {"a": ["b", "c"], "b": ["a", "c", "d"], "c": ["a", "b", "d"], "d": ["b", "c"]}
print(euler_status(square))
print(euler_status({"a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]}))
print(euler_status({"a": ["b", "c", "d"], "b": ["a"], "c": ["a"], "d": ["a"]}))
# Output:
# path
# circuit
# none

#Which Tool? A Decision Table

When not to use these tools: a matching with scores or prices on the edges (the best total score, not the most pairs) needs a different method, the Hungarian algorithm, or a min-cost flow.

Edmonds-Karp is easy to write but not the fastest flow code; Dinic's algorithm is a well-known faster choice on large networks. If the graph is undirected, SCC is just connected components, and BFS or Union-Find already does that. And a bridge test on a graph that changes all the time needs a dynamic structure, not a fresh DFS per change.

#Where This Shows Up

• Dependency tools find groups of modules that depend on each other in a loop by computing SCCs. The condensation can then be ordered with topological sort.
• Solvers for 2-SAT, a logic puzzle with clauses of two variables, are built on SCCs of an implication graph.
• Network engineers look for bridges and articulation points to find single points of failure in a topology.
• Assigning students to projects or tasks to workers is bipartite matching. User-item graphs in recommendation systems are bipartite by construction.
• Flow and cut ideas model traffic and supply chains. Min-cut is also used in image segmentation, where the cut separates foreground pixels from background.
• Exam timetabling is graph coloring: courses are vertices, a shared student is an edge, and time slots are colors.

#Common Mistakes

#Try It: Five Problems

#Recap

A strongly connected component is a largest group of vertices that all reach each other. Kosaraju finds them with a DFS finishing order and a second DFS on the reversed graph, in O(V + E) time. The components form a DAG.

Bridges and articulation points come from one DFS with discovery times and low-links, in O(V + E) time. A tree edge from u to v is a bridge when low[v] is greater than tin[u].

A graph is bipartite exactly when it has no odd cycle, and BFS two-coloring tests it in O(V + E).

A maximum matching grows by flipping augmenting paths. Kuhn costs O(V·E), and Hopcroft-Karp costs O(E·√V).

Max-flow uses a residual graph whose undo edges repair early choices. Edmonds-Karp picks the shortest augmenting path by BFS, giving O(V·E²) time whatever the capacities. At the end, the max-flow equals the min-cut.