WOLFRAM|DEMONSTRATIONS PROJECT

The Hungarian Maximum Matching Algorithm

​
size of bipartite graph
6
10
14
18
22
26
30
maximum degree of lower part
2
3
4
5
6
algorithm step
1
2
3
4
5
6
7
8
9
10
11
Given a bipartite graph (one in which all edges go between the two parts), the Hungarian algorithm finds a matching (i.e., a set of disjoint edges) of maximum size. The algorithm starts with any matching
M
(the empty matching is used here) and constructs a tree via a breadth-first search to find an augmenting path: a path
P
that starts and finishes at unmatched vertices whose first and last edges are not in
M
and whose edges alternate being outside and inside
M
. If the search succeeds, then the symmetric difference of
M
and the edges in
P
yield a matching having one more edge than
M
; we make that change and then search again for a new augmenting path. If the search is unsuccessful, then the algorithm terminates and
M
must be the largest-size matching that exists. Further, the tree data provides a vertex cover (i.e., a set of vertices covering all edges). If the tree search is unsuccessful, as it is at the end, then the size of the vertex cover is the same as the size of the matching, which proves that the final matching has the maximum size possible.
In the Demonstration the current matching is shown in light blue, and the current vertex cover in green. In the tree the orange labels correspond to vertices in the cover that lie in the lower half of the graph. Further, the vertices not colored in the tree correspond to the vertices in the upper half of the graph that are not in the covering.