V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

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.

L1L2L3R1R2R3

Begin with every left and right vertex unmatched.

1function hungarian(adj: number[][], nL: number, nR: number): number {
2 const matchR = new Array(nR).fill(-1); // right point init pair init
3 const dfs = (u: number, seen: Set<number>): boolean => {
4 for (const v of adj[u]) { // try try count candidate try digit
5 if (seen.has(v)) continue;
6 seen.add(v);
7 if (matchR[v] < 0 || dfs(matchR[v], seen)) { // empty match, match
8 matchR[v] = u; // match / match
9 return true;
10 }
11 }
12 return false; // fail: fail
13 };
14 let cnt = 0;
15 for (let u = 0; u < nL; u++) // done count left point done augmenting path
16 if (dfs(u, new Set())) cnt++;
17 return cnt; // maximum matching number
18}
match number0
pairing—
1 / 12

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.