Bipartite Matching

Use augmenting paths to reassign occupied partners and increase a bipartite matching one edge at a time.

Core idea

For each left vertex, search for an alternating path that ends at a free right vertex. Flipping unmatched and matched edges along that path increases the matching by one.

Read the visualization

A trial edge highlights the current request. When a right vertex is occupied, recursion follows its partner to find another option; a successful chain flips as one augmentation.

Begin with every left and right vertex unmatched.

1function hungarian(adj: number[][], nL: number, nR: number): number {
const matchR = new Array(nR).fill(-1);  //  right  point init pair init
const dfs = (u: number, seen: Set<number>): boolean => {
  for (const v of adj[u]) {             //  try try count  candidate try digit 
    if (seen.has(v)) continue;
    seen.add(v);
    if (matchR[v] < 0 || dfs(matchR[v], seen)) { //  empty match, match
      matchR[v] = u;                    // match / match
      return true;
    }
  }
  return false;                         // fail: fail
};
let cnt = 0;
for (let u = 0; u < nL; u++)            // done count  left  point done augmenting path 
  if (dfs(u, new Set())) cnt++;
return cnt;                             //  maximum matching  number 
18}

match number: 0
pairing: —

Complexity and tradeoffs

Time: O(VE). Space: O(V). The DFS-based Hungarian method finds maximum cardinality matching; weighted assignment needs a different variant.

Invariant: The green edges always form a valid matching: no vertex is incident to more than one selected edge.

Where it fits

Maximum bipartite matching models worker-job assignment, course selection, and pairing. Weighted assignment and very large sparse graphs use more specialized algorithms.