DEV Community

Dev Cookies
Dev Cookies

Posted on

⚡ Blog 9: Advanced Graph Patterns (Flow, Matching, Bipartite)

This blog covers three powerful categories of problems:

  1. Flow Networks (Max Flow / Min Cut)
  2. Graph Matching (Maximum Matching, Bipartite Matching)
  3. Bipartite Graph Applications (Coloring, Assignment, Scheduling)

1️⃣ Flow Networks (Max Flow / Min Cut)

A flow network is a directed graph where each edge has a capacity, and we want to push as much “flow” from a source (s) to a sink (t) as possible.

  • Max Flow = Maximum possible flow from s → t.
  • Min Cut = Smallest set of edges that, if removed, disconnect s from t.
  • Ford-Fulkerson / Edmonds-Karp Algorithm: Repeatedly send augmenting paths until no more flow can be added.

Java Implementation (Edmonds-Karp using BFS) 

import java.util.*; class MaxFlow { private int n; private int[][] capacity; private List<Integer>[] adj; public MaxFlow(int n) { this.n = n; capacity = new int[n][n]; adj = new List[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); } public void addEdge(int u, int v, int cap) { capacity[u][v] += cap; // Handle multiple edges adj[u].add(v); adj[v].add(u); // Residual graph } private int bfs(int s, int t, int[] parent) { Arrays.fill(parent, -1); parent[s] = s; Queue<int[]> q = new LinkedList<>(); q.add(new int[]{s, Integer.MAX_VALUE}); while (!q.isEmpty()) { int[] cur = q.poll(); int node = cur[0], flow = cur[1]; for (int next : adj[node]) { if (parent[next] == -1 && capacity[node][next] > 0) { parent[next] = node; int newFlow = Math.min(flow, capacity[node][next]); if (next == t) return newFlow; q.add(new int[]{next, newFlow}); } } } return 0; } public int maxFlow(int s, int t) { int flow = 0; int[] parent = new int[n]; int newFlow; while ((newFlow = bfs(s, t, parent)) > 0) { flow += newFlow; int cur = t; while (cur != s) { int prev = parent[cur]; capacity[prev][cur] -= newFlow; capacity[cur][prev] += newFlow; cur = prev; } } return flow; } }
Enter fullscreen mode Exit fullscreen mode

📌 Example Problems:

  • Maximum Bipartite Matching (via Flow)
  • Network Bandwidth Optimization
  • Airline Traffic Scheduling
  • Project Assignment

2️⃣ Graph Matching

Graph Matching = selecting edges such that no two edges share a vertex.

  • Maximum Matching = maximum number of matched pairs.
  • Bipartite Matching = matching only across two sets (e.g., jobs ↔ workers).

  • Can be solved via:

    • DFS Augmenting Path (Hungarian Algorithm)
    • Max Flow (Reduction of Matching → Flow)

Example: Bipartite Matching with DFS 

class BipartiteMatching { private int n, m; private List<Integer>[] graph; private int[] matchR; private boolean[] seen; public BipartiteMatching(int n, int m) { this.n = n; // left partition this.m = m; // right partition graph = new List[n]; for (int i = 0; i < n; i++) graph[i] = new ArrayList<>(); } public void addEdge(int u, int v) { graph[u].add(v); // Edge from left u → right v } private boolean bpm(int u) { for (int v : graph[u]) { if (seen[v]) continue; seen[v] = true; if (matchR[v] == -1 || bpm(matchR[v])) { matchR[v] = u; return true; } } return false; } public int maxMatching() { matchR = new int[m]; Arrays.fill(matchR, -1); int result = 0; for (int u = 0; u < n; u++) { seen = new boolean[m]; if (bpm(u)) result++; } return result; } }
Enter fullscreen mode Exit fullscreen mode

📌 Example Problems:

  • Job Assignment (workers → jobs).
  • Stable Marriage Problem.
  • Course Scheduling (students → projects).

3️⃣ Bipartite Graphs

A graph is bipartite if nodes can be divided into two disjoint sets such that every edge connects a node in set A to set B.

Checking if a Graph is Bipartite (using BFS Coloring) 

public boolean isBipartite(int[][] graph) { int n = graph.length; int[] color = new int[n]; Arrays.fill(color, -1); for (int i = 0; i < n; i++) { if (color[i] == -1) { Queue<Integer> q = new LinkedList<>(); q.add(i); color[i] = 0; while (!q.isEmpty()) { int u = q.poll(); for (int v : graph[u]) { if (color[v] == -1) { color[v] = 1 - color[u]; q.add(v); } else if (color[v] == color[u]) { return false; } } } } } return true; }
Enter fullscreen mode Exit fullscreen mode

📌 Example Problems:

  • Graph Coloring
  • Team Formation
  • Odd-Cycle Detection

🧠 Key Takeaways

  • Flow Networks → Max flow, min cut, traffic optimization.
  • Matching → Job assignment, stable marriage, bipartite matching.
  • Bipartite Graphs → Graph coloring, odd cycle detection, DFS/BFS-based verification.

These patterns power advanced graph algorithms that solve real-world optimization and scheduling problems.

Top comments (0)