匈牙利算法 求二分图最大匹配

匈牙利算法

1. 二分图

二分图： 又称作二部图，是图论中一种特殊模型。设G=（V，E）是一个无向图，如果顶点V可分割为两个互不相交的子集（A，B），并且图中每条边所关联的两个顶点 i 和 j 分别属于这两个不同的顶点集（$i\in A,j\in B$），则称图G为一个二分图。

简单来说，如果图中所有顶点可以被分为两个集合，图中所有的边的头和尾不属于同一个顶点集合，而是跨越两个集合，则这个图是一个二分图。

二分图当且仅当图中不含奇数环

• 如何判断二分图？染色法

  // 判断从某个节点出发，是否所有连通节点都满足相邻节点不同颜色
  bool dfs(std::vector<std::vector<int>> &graph, std::vector<int> &st, int i, int color)
  {
      // 之前被染色的情况
      if (st[i])
      {
          if (st[i] == color) return true;
          else return false;  // st[i] != color 矛盾
      }
      
      st[i] = color;
      
      for (int j: graph[i])
      {
          // 颜色1、2之间的切换可以用3-color
          if(!dfs(graph, st, j, 3 - color)) return false;
      }
      return true;
  }
  
  // 检查邻接表graph是否为二分图
  bool check(std::vector<std::vector<int>> &graph)
  {
      int n = graph.size();
      std::vector<int> st(n, 0);		// st: 标记染色，0(未染色)，1和2为相邻节点颜色。
      bool ans = true;
      
      for (int i = 0; i < n; i ++)
      {
          if (!st[i] && !dfs(graph, st, i, 1))
          {
              ans = false;
              break;
          }
      }
      return ans;
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37

  import sys
  # 设置递归栈次数
  sys.setrecursionlimit(100000)
  
  def dfs(graph, st, i, color):
      if st[i]:
          if st[i] == color:
              return True
          else:
              return False
      st[i] = color
      
      for j in graph[i]:
          if not dfs(graph, st, j, 3 - color):
              return False
      
      return True
  
  def check(graph):
      n = len(graph)
      st = [0 for _ in range(n)]
      ret = True
      
      for i in range(n):
          if not st[i] and not dfs(graph, st, i, 1):
              ret = False
              break
      return ret
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28

2. 匹配

• **匹配：**在图论中，一个匹配（matching）是指一个边的集合，其中任意两条边都没有公共顶点。
• **最大匹配：**一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。
• **完美匹配：**如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配，但并非每个图都存在完美匹配。

3. 路径

• **交替路径：**从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径称为交替路径。
• **增广路径：**从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。
• 增广路径的性质：
  • P的路径长度必定为奇数，第一条边和最后一条边都不属于M，因为两个端点分属两个集合，且未匹配。
  • P经过取反操作可以得到一个更大的匹配M’。
  • M为G的最大匹配当且仅当不存在相对于M的增广路径。

4. 匈牙利算法

• **匈牙利算法：**利用增广路径求二分图的最大匹配算法称作匈牙利算法。（匈牙利数学家Edmonds于1965年提出）。
• **基本思想：**通过寻找增广路径，把增广路径中的匹配边和非匹配边的相互交换，这样就会多出一条匹配边，直到找不到增广路径为止。

// find: 对于集合1的点i，找集合2的匹配对象，成功返回true
// graph: 邻接表
// match: 记录集合2的匹配对象，没有匹配为-1
bool find(std::vector<std::vector<int>> &graph, std::vector<int> &macth, std::vector<bool> &st, int i)
{
    
    for (int j: graph[i])
    {
        // 已经访问了集合2的对象j，那么跳过
        if (st[j]) continue;
        st[j] = true;
        // j没有被匹配或者j之前的匹配对象macth[j]可以另外被配对
        if (macth[j] == -1 || find(graph, macth, st, macth[j]))
        {
            macth[j] = i;
            return true;
        }
    }
    return false;
}
// hungarian: 求二分图最大匹配，返回最大匹配数量
// graph: 邻接表
// n1: 集合1大小
// n2: 集合2大小
int hungarian(std::vector<std::vector<int>> &graph, int n1, int n2)
{
    int ans = 0;
   	// match: 记录集合2的匹配对象，没有匹配为-1
    std::vector<int> macth(n2, -1);
    
    for (int i = 0; i < n1; i ++)
    {
        // st: 记录每次查找是否访问了集合2中的对象
        std::vector<bool> st(n1, false);
        if (find(graph, macth, st, i)) ans ++;
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

def find(graph, macth, st, i):
    for j in graph[i]:
        if st[j]:
            continue
        
        st[j] = True
        if macth[j] == -1 or find(graph, macth, st, macth[j]):
            macth[j] = i
            return True
    return False
    
def hungarian(graph, n1, n2):
    ans = 0
    match = [-1 for _ in range(n2)]
    
    for i in range(n1):
        st = [False for _ in range(n2)]    
        if find(graph, match, st, i):
            ans += 1
        
    return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5. 算法应用

SORT算法原理（匈牙利匹配+卡尔曼滤波跟踪）