2

有这个库实现了许多算法，其中之一是最大二分匹配。

这是源代码的链接： http: //shygypsy.com/tools/bpm.cpp

我也会把它包括在这里（没有评论）

#include <string.h>

#define M 128
#define N 128

bool graph[M][N];
bool seen[N];
int matchL[M], matchR[N];
int n, m;

bool bpm( int u )
 {
  for( int v = 0; v < n; v++ ) 
   if( graph[u][v] )
   {
    if( seen[v] ) continue;
    seen[v] = true;

    if( matchR[v] < 0 || bpm( matchR[v] ) )
    {
        matchL[u] = v;
        matchR[v] = u;
        return true;
    }
}
return false;
}

int main()
{
  memset( matchL, -1, sizeof( matchL ) );
  memset( matchR, -1, sizeof( matchR ) );
  int cnt = 0;
  for( int i = 0; i < m; i++ )
  {
      memset( seen, 0, sizeof( seen ) );
      if( bpm( i ) ) cnt++;
  }
  return 0;
}

我们有一个运行m时间的 for 循环。这个数字m是指工人的数量。然后我们进入bpm有另一个for循环的函数。这个循环运行的n时间n是任务的数量。

到目前为止，我们有m*n时间复杂度。

然而，bpm在第三个 if 语句中有一个递归函数调用。此函数的目标是运行 adfs以找到增强的路径。

我知道这dfs有时间复杂度O(n+m)。所以我会假设该函数bpm的复杂性为O(n+m)

因此总时间复杂度为O(m*(n+m))

但是作者说它是O(m*n^2). 有人可以解释一下为什么会这样吗？先感谢您！

4

1 回答 1

3

这里的变量有些令人困惑：M 和 N 指的是图每一侧的节点数。DFS 的运行时间是O(E+V)其中 E 是边数。在二分图中 |E| 最多为 N*M，V 为 (N+M)，因此您的 DFS 将采用O(NM). 则总时间复杂度为O(NM^2)。不知道在哪里N^2进来，可能是一个错字...

于 2013-03-10T19:32:59.337 回答