# Data Structures: Graph Theory- Hungarian Algorithm

Page 1 of 1

## 0 Replies - 17730 Views - Last Post: 29 December 2012 - 12:43 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=305150&amp;s=3bc2842baad3d38db80d9a0166f89978&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 macosxnerd101

• Self-Trained Economist

Reputation: 10486
• Posts: 38,857
• Joined: 27-December 08

# Data Structures: Graph Theory- Hungarian Algorithm

Posted 29 December 2012 - 12:43 PM

The Hungarian algorithm is used to optimize a graph, represented as a bipartite cost matrix. As such, the Hungarian algorithm utilizes the bipartite matching algorithm. An application of the Hungarian algorithm is to find the best worker for the best job.

The matrix is set up in the following form:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 4   5   5   4   6
B  | 6   7   7   5   8
C  | 6   5   2   5   4
D  | 4   3   4   7   6
E  | 9   7   7   6   10

```

The steps of the Hungarian algorithm are as follows:
-If the matrix isn't square, make it square by adding rows of 0's
-Reduce the matrix (note that this is NOT a Linear Algebra reduction)
-Pick a greedy matching on the 0's
-Find the optimal matching with the bipartite matching algorithm
-If the matching isn't optimal, find the minimal Cover (found X vertices + unfound Y vertices).
-Based on the cover, find the minimal uncovered entry (call it m). Subtract m from every uncovered entry and add m to every double-covered entry.
-Pick a new greedy matching on the 0's and repeat

Some Pseudo-Code:
```function hungarianAlgorithm(SquareCostMatrix matrix)
foreach row in matrix
min = findMin(row)

foreach element in row
element <-- element - min
end foreach
end foreach

foreach column in matrix
min = findMin(col)

if min > 0
foreach element in column
element <-- element - min
end foreach
end if
end foreach

while matrix.getNumberMatches() < matrix.getX().size()
pickMatching(matrix)
augmentMatching(matrix)

minCover <-- matrix.getMinCover()

foreach element in minCover
if matrix.x.contains(element)
cover row at element
end if

else
cover column at element
end else
end foreach

min <-- findMinUncovered(matrix)

foreach row in matrix
foreach element in row
if isCovered(element) == FALSE
element <-- element - min
end if

else if isDoubleCovered(element)
element <-- element + min
end if
end foreach
end foreach
end while
end function

function findMinUncovered(Matrix matrix)

min <-- infinity

foreach row in matrix
foreach element in row
if isCovered(element) == FALSE AND element < min
min <-- element
end foreach
end foreach

return min
end foreach

function pickMatching(Matrix matrix)
foreach row in matrix
foreach element in row, indexed i
if element == 0 AND hasMatching(column[i]) == FALSE
match(element)
end if
end foreach
end foreach
end function

```

Now, let's work through an example with the following cost matrix:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 4   5   5   4   6
B  | 6   7   7   5   8
C  | 6   5   2   5   4
D  | 4   3   4   7   6
E  | 9   7   7   6   10

```

Each row has the following minimums:
A- 4
B- 4
C- 2
D- 3
E- 6

After subtracting the row minimums from each row, the matrix reduces to:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 0   1   1   0   2
B  | 1   2   2   0   3
C  | 4   3   0   3   2
D  | 1   0   1   4   3
E  | 3   1   1   0   4

```

The only non-zero column minimum is at column 5, where the min = 2. Reducing the matrix again, we get:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 0   1   1   0   0
B  | 1   2   2   0   1
C  | 4   3   0   3   0
D  | 1   0   1   4   1
E  | 3   1   1   0   2

```

Picking a greedy matching (using a * to denote a matched edge) on the 0's, we get:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 0*  1   1   0   0
B  | 1   2   2   0*  1
C  | 4   3   0*  3   0
D  | 1   0*  1   4   1
E  | 3   1   1   0   2

```

The bipartite matching algorithm produces the forest: E --- 4 -*- B, meaning the matching is maximal. So it is necessary to reduce the matrix yet again. The min cover for this matching is: {4, A, C, D}. The double-covered elements are A4, C4, and D4. The remaining elements in the A, C, and D rows are single covered, as are the remaining elements in column 4.

The minimum amongst the uncovered elements is 1, so subtract it from the uncovered elements and add it to the double-covered elements. The updated matrix is as follows, with the greedy matching the same as the last one:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 0*  1   1   1   0
B  | 0   1   1   0*  0
C  | 4   3   0*  4   0
D  | 1   0*  1   5   1
E  | 2   0   0   0   1

```

Augmenting the matching leaves the final matrix:
```X/Y | 1 | 2 | 3 | 4 | 5
A  | 0*  1   1   1   0
B  | 0   1   1   0*  0
C  | 4   3   0   4   0*
D  | 1   0*  1   5   1
E  | 2   0   0*  0   1

```

Looking at the original cost matrix, that leaves the final cost at:
3 + 2 + 6 + 4 + 3 = 18

Is This A Good Question/Topic? 0

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }