Lesson 37.3 · Advanced Graph Algorithms
Bipartite Graphs, Euler Paths and Maximum Flow
Two-colour a graph with BFS; walk every edge once with Hierholzer's algorithm; push the most flow from s to t with augmenting paths.
16 min
Think of it like this
Bipartite: seating guests at two tables so no two enemies share a table. Euler path: a postman who must walk every street exactly once. Max flow: the most water per second that a network of pipes can carry from a reservoir to a city.
1.Bipartite check
BFS each component, colouring neighbours with the opposite colour. An edge between two same-coloured nodes means an odd cycle, so the graph isn't bipartite. O(V + E).
2.Euler paths (Hierholzer)
A directed graph has an Euler path when at most one node has out − in = 1 (the start), at most one has in − out = 1 (the end), and the rest are balanced. Hierholzer: DFS consuming edges; when a node has no unused edges left, append it to the route. Reverse at the end. Choosing neighbours in sorted order gives the lexicographically smallest route.
3.Maximum flow (Edmonds-Karp)
Keep residual capacities. Repeatedly BFS from s to t through edges with remaining capacity, find the bottleneck, and push it: subtract along the path and add to the reverse edges (so later paths can undo earlier choices). Stop when t is unreachable. O(V × E²); the result also equals the minimum cut (max-flow min-cut theorem).
Bipartite matching is max flow with unit capacities from a source to the left side and from the right side to a sink.
4.A* search
Dijkstra ordered by g + h, where h estimates the remaining cost and never overestimates (admissible). It explores toward the goal first and still returns optimal paths. On puzzle state graphs (sliding tiles), Manhattan distance is the usual heuristic.
Remember
- Odd cycle ⇔ not bipartite.
- Euler: degree conditions + Hierholzer.
- Augmenting paths with reverse edges; max flow = min cut.
Common mistakes
- Forgetting reverse residual edges in max flow.
- Using an overestimating heuristic in A*.