数据结构与算法--二分匹配

1import numpy as np
2
3def hungarian_algorithm(cost_matrix):
4    def _make_cover_zero(matrix):
5        n = len(matrix)
6        for i in range(n):
7            minval = min(matrix[i])
8            matrix[i] -= minval
9        return sum(minval for minval in matrix.flat)
10
11    def _augment_path(matrix, parents, u):
12        if parents[u] < 0:
13            return True
14        v = parents[u]
15        _augment_path(matrix, parents, parents[v])
16        matrix[u][v], matrix[v][u] = matrix[v][u], matrix[u][v]
17        return False
18
19    n = len(cost_matrix)
20    matrix = cost_matrix.copy()
21    parents = [-1] * n
22    cover = 0
23
24    while True:
25        cover += _make_cover_zero(matrix)
26        queue = [i for i in range(n) if parents[i] < 0]
27        while queue:
28            u = queue.pop(0)
29            for v in range(n):
30                if matrix[u][v] == 0 and parents[v] < 0:
31                    parents[v] = u
32                    if _augment_path(matrix, parents, v):
33                        return cover
34        if not any(parents[i] < 0 for i in range(n)):
35            break
36
37    return cover
38
39# 使用示例
40cost_matrix = np.array([[0, 5, 9], 
41                       [4, 0, 7], 
42                       [8, 2, 0]])
43print(hungarian_algorithm(cost_matrix))  # 输出匹配的边数