如何修改算法以获得二部图中的所有最大匹配？

Question

我使用下面的代码在二分图中找到最大匹配（我试着添加了一些评论）：

#include <iostream>

using namespace std;

// definition of lists elements
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// definition objective type queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      
    ~queue();     
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

queue::queue()
{
  head = tail = NULL;
}

queue::~queue()
{
  while(head) pop();
}

bool queue::empty(void)
{
  return !head;
}

int queue::front(void)
{
  if(head) return head->data;
  else     return -10000;
}

void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// main part
//---------------

queue Q;                          // queue
int *Color;                       // colors of vertexes
slistEl **graf;                   // adjacency array
int **C;                          // matrix of capacity
int **F;                          // matrix of nett flow
int *P;                           // array of prev
int *CFP;                         // array of residual capacity
int n,m,fmax,cp,v,u,i,j;          // 
bool esc;                         // 
slistEl *pr, *rr;                 // pointer for list elements


int main(int argc, char *argv[])
{

  // n - number of vertexes
  // m - number of edges

  cin >> n >> m;


  Color = new int [n];             
  graf = new slistEl * [n];       
  for(i = 0; i < n; i++)
  {
    graf[i] = NULL;
    Color[i] = 0;
  }

  C = new int * [n+2];            
  F = new int * [n+2];            
  for(i = 0; i <= n + 1; i++)
  {
    C[i] = new int [n+2];
    F[i] = new int [n+2];
    for(j = 0; j <= n + 1; j++)
    {
      C[i][j] = 0;
      F[i][j] = 0;
    }
  }

  P = new int [n+2];             
  CFP = new int [n+2];           

  // reading edges definition and adding to adjacency list

  for(i = 0; i < m; i++)
  {
    cin >> v >> u;
    pr = new slistEl;
    pr->data = u;
    pr->next = graf[v];
    graf[v]  = pr;

    pr = new slistEl;
    pr->data = v;
    pr->next = graf[u];
    graf[u]  = pr;
  }

for(i = 0; i < n; i++){
         cin>> Color[i];
      }



    for(i = 0; i < n; i++)
      if(Color[i] == -1)
      {
        for(pr = graf[i]; pr; pr = pr -> next) // neighbours of blue
          C[i][pr->data] = 1;     // capacity to red
        C[n][i] = 1;              // capacity  to source
      }
      else C[i][n+1] = 1;         // capacity edges to outfall

    //**  Edmonds-Karp algorithm **

    fmax = 0;

    while(true)
    {
      for(i = 0; i <= n + 1; i++) P[i] = -1;

      P[n] = -2;
      CFP[n] = MAXINT;

      while(!Q.empty()) Q.pop();
      Q.push(n);

      esc = false;

      while(!Q.empty())
      {
        v = Q.front(); Q.pop();

        for(u = 0; u <= n + 1; u++)
        {
          cp = C[v][u] - F[v][u];
          if(cp && (P[u] == -1))
          {
            P[u] = v;
            if(CFP[v] > cp) CFP[u] = cp; else CFP[u] = CFP[v];
            if(u == n+1)
            {
              fmax += CFP[n+1];
              i = u;
              while(i != n)
              {
                v = P[i];
                F[v][i] += CFP[n+1];
                F[i][v] -= CFP[n+1];
                i = v;
              }
              esc = true; break;
            }
            Q.push(u);
          }
        }
        if(esc) break;
      }
      if(!esc) break;
    }

    // showing reuslts


    if(fmax > 0)
      for(v = 0; v < n; v++)
        for(u = 0; u < n; u++)
          if((C[v][u] == 1) && (F[v][u] == 1))
            cout << v << " - " << u << endl;

  cout << endl;

  // cleaning

  delete [] Color;               

  for(i = 0; i < n; i++)
  {
    pr = graf[i];
    while(pr)
    {
      rr = pr;
      pr = pr->next;
      delete rr;
    }
  }

  delete [] graf;               

  for(i = 0; i <= n + 1; i++)
  {
    delete [] C[i];
    delete [] F[i];
  }
  delete [] C;                    
  delete [] F;                    

  delete [] P;                  
  delete [] CFP;                

  return 0;
}

它returns只有一个最大匹配。例如数据：

6 7
0 3 0 5
1 3 1 4 1 5
2 3 2 5
1 1 1 -1 -1 -1

但是有更多的最大匹配。

我不知道，我应该如何修改它才能获得所有结果，我想请人帮忙。提前谢谢你。

Answer 1

该算法只对获得最大匹配有效。

如果你想要所有最大匹配，你必须考虑任何匹配都是最大匹配的情况。在那种情况下，你有 N!可能性。

由于您需要访问所有解决方案，因此您的复杂度至少为 O(N!)。因此，忘记你的代码，你可以使用递归算法尝试所有可能的匹配，并保留你得到的最大匹配集。

如何修改算法以获得二部图中的所有最大匹配？

How to modify algorithm to get all maximal matchings in bipartite graph?

algorithm

graph-theory

matching