有关二部图KM算法的讨论

1. KM算法：百度​​http://baike.baidu.com/view/739278.htm​​

2. 我对KM算法的看法：

我觉得KM算法有错误，它是先构造出相等子图，然后在相等子图中找完备匹配，如果找到，那么此完备匹配必然是这个二部图的最优匹配

反之，若相等子图找不到完备匹配，是不是原二部图就不存在最优匹配？

3. 个人提成的算法：

我的算法是枚举法，举例说明：

如图：假如已经有一个图，我设计了一个系统，首先把此图作为输入，然后能够判断它是不是二部图，判断的方法是利用图的深度优先遍历，将相邻接的两个顶点打上不同的颜色，遍历完毕后，如果所有相邻接的顶点颜色相反，比如一个是红色，另一个是蓝色，那么此图是二部图，如果有顶点没有边相连，那么此顶点是孤立点。如果此图是二部图，我的系统可以将所有顶点划分为红点集合蓝点集，比如0,1,2，属于红点集，3,4,5属于蓝点集。孤立点属于孤立点集。

接着我设计的系统可以利用匈牙利算法找出此二部图的完备匹配，和最优匹配，最优匹配采用枚举法，比如，上图，从红点集中每个红点找，0和3匹配，那么1和在剩余的4,5,中去找匹配的，比如1和4匹配，那么2只有去5找匹配，下一轮，0和4匹配，1从剩余的蓝点中找匹配，依次类推，这就是枚举法，这种方法一定可以找到最优匹配。

我设计的图把链接矩阵和邻接链表混合起来使用，支持无向，有向，有权，无权图

具体代码如下：

图类代码：

/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:图类头文件
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*Date: 2012/10/11
*/
#ifndef GRAPH_H
#define GRAPH_H

const int maxvertex=100; //最多可以有100个顶点
const int maxedge=1000;  //最多可以有1000条边
const double maxweight=1e10; //权值最大值

#include <iostream>
#include <cstdlib>
#include <memory>

using namespace std;

template<class ElemType>
class Graph {
  private:
    bool IsDirect; //是否是有向图,false表示无向图
    bool IsWeight; //是否带权图
  protected:
    typedef struct lnode { //邻接链表结点
      int sequence; //顶点的序号0,1,2,...
      struct lnode *next;
    };
    typedef struct tnode { //表结点
      ElemType vertex; //顶点的值
      lnode *link;
    };
    typedef struct Graph_struct {
      tnode *array;
      double **connect; //邻接矩阵,矩阵元素是边上的权值
      int edgenum;  //图的边数
      int vertexnum; //图的顶点数
    };
    Graph_struct graph;
    bool *visited; //记录顶点是否被访问过
    void DFSTranverse(int start);
    void Get(int index,ElemType& e); //根据索引号获取顶点 
  public:
    Graph(bool IsDirect,bool IsWeight); 
    void DFS();
    void show();
    virtual ~Graph();
};
#endif

图类实现代码：

/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:图类实现代码
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*Date: 2012/10/11
*/
#include "Graph.h"

template<class ElemType>

Graph<ElemType>::Graph(bool IsDirect,bool IsWeight) {
  this->IsDirect=IsDirect;
  this->IsWeight=IsWeight;

  int n;
  int i,j;

  cout<<"请输入图的顶点数:";
  cin>>n;

  if(!cin.good()) {
    cerr<<"输入参数格式不合法!"<<endl;
    return;
  }

  if(n<=0 || n>maxvertex) {
    cerr<<"顶点数应该大于0且小于"<<maxvertex<<endl;
    return;
  }
  graph.vertexnum=n;

  graph.connect=new double*[graph.vertexnum];
  for(i=0;i<graph.vertexnum;i++) {
    graph.connect[i]=new double[graph.vertexnum]; 
  }

  for(i=0;i<graph.vertexnum;i++) {
    for(j=0;j<graph.vertexnum;j++) graph.connect[i][j]=0;
  }

  this->visited=new bool[graph.vertexnum];
  
  graph.array=new tnode[graph.vertexnum];
  if(!graph.array) {
    cerr<<"内存分配失败!"<<endl;
    return;
  }

  cout<<"请输入顶点信息"<<endl;
  ElemType vertex;
  for(i=0;i<graph.vertexnum;i++) {
    cout<<"请输入第"<<i<<"个顶点:";
    cin>>vertex;
    if(!cin.good()) {
    cerr<<"输入顶点格式不合法!"<<endl;
    i--;
    continue;
    }
    else {
      graph.array[i].vertex=vertex;
      graph.array[i].link=0;
    }
  }

  cout<<"请输入边信息"<<endl;
  int m=0;
  int from; //边的起点
  int to;  //边的终点
  double weight;

  cout<<"如果输入边的起点或终点是-1时,则程序停止接受输入!"<<endl;
  
  int k=0; //边的个数
  lnode *p;
  while(true) {
    cout<<"边的起点:";
    cin>>from;
    if(!cin.good()) {
      cerr<<"输入起点不合法!"<<endl;
      break;;
    }
    if(from==-1) break;
    else if(from<0 || from>=graph.vertexnum) {
      cerr<<"输入范围应该大于等于0且小于"<<graph.vertexnum<<endl;
      break;;
    }

    cout<<"边的终点:";
    cin>>to;
    if(!cin.good()) {
      cerr<<"输入终点不合法!"<<endl;
      break;
    } 
    if(to==-1) break;
    else if(to<0 || to>=graph.vertexnum) {
      cerr<<"输入范围应该大于等于0且小于"<<graph.vertexnum<<endl;
      return;
    }

    if(IsWeight==true) {
      cout<<"输入边的权值:";
      cin>>weight;
      if(!cin.good()) {
        cout<<"输入权值不合法!"<<endl;
        break;
      }
      if(weight>=maxweight || weight<0) {
        cerr<<"权值应该大于等于0且小于"<<maxweight<<endl;
        break;
      }
    }
    p=new lnode;
    p->next=0;
    p->sequence=to;
    if(IsWeight) graph.connect[from][to]=weight;
    else graph.connect[from][to]=1;

    p->next=graph.array[from].link; //插入邻接链表
    graph.array[from].link=p;

    if(!IsDirect) { //是无向图
      lnode *q=new lnode;
      q->next=0;
      q->sequence=from;
      if(IsWeight) graph.connect[to][from]=weight;
      else graph.connect[to][from]=1;

      q->next=graph.array[to].link;
      graph.array[to].link=q;
    }
    k++;
  }
  graph.edgenum=k;
}

template<class ElemType>
void Graph<ElemType>::DFS() {
  int i;
  for(i=0;i<graph.vertexnum;i++) {
    this->visited[i]=false;
  }
  for(i=0;i<graph.vertexnum;i++) {
    if(visited[i]==false) DFSTranverse(i);
  }
}

template<class ElemType>
void Graph<ElemType>::DFSTranverse(int start) {
  visited[start]=true;
  cout<<"第"<<start<<"个顶点是:"<<graph.array[start].vertex<<endl;
  int j;
  lnode *p=graph.array[start].link;
  while(p) {
    j=p->sequence;
    if(!this->visited[j]) DFSTranverse(j);
    p=p->next;
  }
}

template<class ElemType>
void Graph<ElemType>::Get(int index,ElemType &e) {
  if(index<0 || index>=graph.vertexnum) {
    cerr<<"索引号应该大于等于0且小于"<<graph.vertexnum<<endl;
    exit(1);
  }
  e=graph.array[index].vertex;
}

template<class ElemType>
void Graph<ElemType>::show() {
  int m,n;
  double weight;

  n=graph.vertexnum;
  m=graph.edgenum;

  cout<<"图有"<<n<<"个顶点,"<<m<<"条边"<<endl;
  cout<<"图的顶点信息:"<<endl;
  this->DFS();

  int i,j;
  int from,to;
  int k=1;

  ElemType e;

  cout<<"图的边信息:"<<endl;
  for(i=0;i<n;i++) {
    for(j=0;j<n;j++) {
      if(graph.connect[i][j]) { 
        from=i;
        to=j;
        cout<<endl;
        cout<<"第"<<k++<<"条边"<<endl;
        cout<<"起点:";
        e=graph.array[from].vertex;
        cout<<e<<" ";
        cout<<"终点:";
        e=graph.array[to].vertex;
        cout<<e<<" ";
        if(IsWeight)
        {
          weight=graph.connect[i][j];
          cout<<"权值:"<<weight<<endl;
        }
      }
    }
  }
}

template<class ElemType>
Graph<ElemType>::~Graph() {
  delete []visited;
  visited=0;
  int i;
  lnode *p,*q;
  for(i=0;i<graph.vertexnum;i++) {
    p=graph.array[i].link;
    while(p) {
      q=p;
      p=p->next;
      graph.array[i].link=p;
      delete q;
    }
  }
  delete []graph.array;
  graph.array=0;
  for(i=0;i<graph.vertexnum;i++) {
    delete []graph.connect[i];
    graph.connect[i]=0;
  }
  delete graph.connect;
  graph.connect=0;
}

二部图代码：

/*
This is a free Program, You can modify or redistribute it under the terms of GNU
*Description:输入一个图,能够识别该图是不是二部图,如果是,自动将此二部图的顶点划分为
红点集合蓝点集,并确保红点集中元素个数小于等于蓝点集中元素的个数,
此系统核心功能还包括找出二部图完备匹配和最优匹配
*Language: C++
*Development Environment: VC6.0
*Author: Wangzhicheng
*Date: 2012/10/11
*/

#include "graph.h"
#include "graph.cpp"
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <set>
using namespace std;

enum Color{red,blue,black};  //定义颜色

/*
二部图类,是图的公有派生类
*/
template<class ElemType>
class Bipartite_Graph:public Graph<ElemType> {
  private:
    bool flag;        //表示此图是不是二分图
    bool isolateflag;       //表示此图是否有孤立点
    bool perfectMatch;      //表示此图有没有完备匹配
    vector<int>Red;     //红点集向量
    vector<int>Blue;    //蓝点集向量
    vector<int>isolate;     //孤立点集合 
    Color *vertexcolor;   //颜色向量,向量中每个元素为相应顶点的颜色
    map<int,int>match;    //<蓝点,与蓝点匹配的红点>
    int count;        //此二部图的匹配数
        /*********************************************************/
    stack<pair<int,int> >Stack;  //保存着匹配
    stack<pair<int,int> >tempStack;  //临时保存Stack内容
    vector<pair<stack<pair<int,int> >,int> >MatchArray;  //存放所有匹配和其对应的权值和的向量

  public:
    /*
    二部图的构造方法,在构造方法中,完成识别二部图的功能,划分出红点集合蓝点集的功能
    */
    Bipartite_Graph(bool IsDirect,bool IsWeight):Graph<ElemType>(IsDirect,IsWeight) {
      vertexcolor=new Color[graph.vertexnum];
      isolateflag=false;
      flag=true;
      perfectMatch=true;
      count=0;
      int i,j;
      for(i=0;i<graph.vertexnum;i++) vertexcolor[i]=black; //将所有顶点都打上黑色
      for(i=0;i<graph.vertexnum;i++) visited[i]=false;  //将所有顶点都设置为未访问
      for(i=0;i<graph.vertexnum;i++) {
        if(visited[i]==false) {
          IsBipartite_Graph_DFS(i,red);  //判断输入的图是不是二部图,如果是,则将图的顶点划分为红点集和蓝点集
          if(flag==false) return;  //IsBipartite_Graph_DFS执行后,如果输入的图不是二部图,则flag==false
        }
      }
      Exchange();  //如果需要,交换红点集合蓝点集
      count=0;
      vector<int>::iterator it;
      /*
      初始化时,将每个匹配设置为<蓝点,-1>,即蓝点对应的红点为-1
      */
      for(it=Blue.begin();it!=Blue.end();it++) {
        pair<int,int>p(*it,-1); // <蓝点,-1>
        match.insert(p);
      }
      
    }
    /*
    匈牙利算法,其核心思想是对于红点集中每一个红点,到蓝点集中找出所有的增广路径,找到就增广
    从而不断扩充原有的匹配,如果红点集中每个红点都找到匹配,即其所对应的蓝点,则程序找到
    完备匹配
    */
    void Hungary() {  
      vector<int>::iterator it;

if(isolateflag==true || flag==false)  {
                              if(flag==false) {
                              cerr<<"不是二部图!"<<endl;
                              return;
                        }
                        else {
                          cerr<<"此二部图存在孤立点,找不到最优匹配!"<<endl;
                           return;
                        }
                     }

if(isolateflag==true) {
        cerr<<"此二部图存在孤立点,找不到完备匹配!"<<endl;
        return;
      }
      for(it=Red.begin();it!=Red.end();it++) {
        /*
        每次到蓝点集中找增广路径之前,都将所有蓝点设为为未访问
        这样才能找到完备匹配
        */
        for(int i=0;i<graph.vertexnum;i++) visited[i]=false;
          if(DFS(*it)) count++;
      }
      if(count<Red.size()) {  //此时至少有一个红点没有与其匹配的蓝点
        cerr<<"此二部图不存在完备匹配!"<<endl;
        perfectMatch=false;
        return;
      }
      ElemType red,blue;
      cout<<"完备匹配是:"<<endl;
      map<int,int>::iterator pos;
      for(pos=match.begin();pos!=match.end();pos++) {
        if(pos->first==-1 || pos->second==-1) continue;  //此时match中有顶点没有匹配
        Get(pos->first,blue);  
        Get(pos->second,red);  
        cout<<"红点:"<<red<<"到"<<"蓝点"<<blue<<endl;
      }
      cout<<"共有"<<count<<"个匹配"<<endl;
    }
    /*
    显示二部图的红点集合蓝点集
    */
    void show() {
      Graph<ElemType>::show();
      vector<int>::iterator it;
      cout<<endl<<"红点集是:"<<endl;
      for(it=Red.begin();it!=Red.end();it++) {
        cout<<*it<<" ";
      }
      cout<<endl;
      cout<<endl<<"蓝点集是:"<<endl;
      for(it=Blue.begin();it!=Blue.end();it++) {
        cout<<*it<<" ";
      }
      cout<<endl;
      if(isolateflag) {
        cout<<endl<<"孤立点是:"<<endl;
        for(it=isolate.begin();it!=isolate.end();it++) {
          cout<<*it<<" ";
        }
      }
      cout<<endl;
    }
    ~Bipartite_Graph() {
      delete []vertexcolor;
      int i;
    }
  /**********************************************************************/
    /*
    此方法找出最优匹配,核心思想是利用枚举法,当某个红点i在蓝点集中找到匹配时,
    下一个红点i+1从未访问过的蓝点中找匹配
    */
    void OptimalMatch() {
      int i,k;
            if(isolateflag==true || flag==false)  {

if(flag==false) {
                              cerr<<"不是二部图!"<<endl;
                              return;
                        }
                        else {
                                cerr<<"此二部图存在孤立点,找不到最优匹配!"<<endl;
                                return;
                             }

}

for(i=0;i<graph.vertexnum;i++) visited[i]=false;
      k=0;  //k表示匹配数
      perfectMatch=false;
      vector<int>::iterator it=Red.begin();
      DFS(it,k);
      if(perfectMatch==false) {
        cerr<<"该二部图不存在完备匹配!"<<endl;
        return;
      }
      int maxpos;
      int maxweight=0;
      for(i=0;i<MatchArray.size();i++) {
        if(MatchArray[i].second>maxweight) {
          maxweight=MatchArray[i].second;
          maxpos=i;
        }
      }
      cout<<"最优匹配是:"<<endl;
      stack<pair<int,int> > s=MatchArray[maxpos].first;
      while(s.empty()==false) {
        int red=s.top().first;
        int blue=s.top().second;
        cout<<"红点:"<<red<<"--"<<"蓝点:"<<blue<<endl;
        s.pop();
      }
      cout<<"权值和为:"<<maxweight<<endl;
    }
  private:
    void Exchange() {
      if(Red.size()<=Blue.size()) return;
      //swap(Red,Blue); //交换两个向量的内容,这样在使用匈牙利算法时可节省查找增广路径的时间
      Red.swap(Blue);
    }
    /*
    此方法识别输入图是不是二部图,核心思想是通过图的深度优先遍历,对每个顶点进行着色,
    如果相邻接的两个顶点颜色一致,则该图不是二部图
    @start: 选择一个开始的顶点进行深度优先遍历
    @Color: 当前被访问顶点的颜色
    */
    void IsBipartite_Graph_DFS(int start,Color color) {  //pre是顶点start在DFS序列中的直接前驱顶点
      int j;
      visited[start]=true;    
      lnode *p=graph.array[start].link;
      /*
       找到孤立点 
      */
      if(!p) {
        isolateflag=true;         
          isolate.push_back(start);  //加入孤立点集合
        return;
      }
      if(vertexcolor[start]==black) {  //此顶点没有打上颜色
        vertexcolor[start]=color;
        if(color==red) {
          Red.push_back(start);  //将此顶点加入红点集
          color=blue;  //将颜色转化
        }
        else {
          Blue.push_back(start);
          color=red;
        }
      }
      while(p) {
        j=p->sequence;
        if(!visited[j]) {
          if(flag==true) IsBipartite_Graph_DFS(j,color); //去检查此顶点的相邻顶点
        }
        else {
          if(vertexcolor[j]==vertexcolor[start]) {  //相关联的两个顶点颜色一样,则此图不是二分图
            cerr<<"不是二分图!"<<endl;
            Red.clear();
            Blue.clear();
            flag=false;
            return;
          }
        }
        p=p->next;
      }
    }
    /*
    此方法根据红点k,在蓝点集中找到增广路径,找到就增广
    @k: 红点
    */
    bool DFS(int k) {
      vector<int>::iterator it;
      for(it=Blue.begin();it!=Blue.end();it++)  //试探每一个蓝点集的顶点
      {
        
        if(graph.connect[k][*it] && !visited[*it])  //如果此蓝点与红点相连,且该蓝点没有被访问过
        {
          visited[*it]=true;
          if(match[*it]==-1 || DFS(match[*it]))  //如果该蓝点没有与其匹配的红点,或者蓝点
                          //有匹配的红点,那么从该红点查找匹配
          {
            match[*it]=k;    //找到增广路径,将其取反
            return true;
          }
        }
      }
      return false;
    }
    /*********************************************************************************/
    void DFS(vector<int>::iterator i,int k) {  //i指向当前的红点,k表示匹配数
      vector<int>::iterator it;
      int weight;
      if(i!=Red.end() && k<Red.size()) {
        for(it=Blue.begin();it!=Blue.end();it++) {
          if(graph.connect[*i][*it] && !visited[*it]) {  //匹配成功
            pair<int,int>p(*i,*it);  //构造一个匹配
            Stack.push(p);  //将此匹配入栈
            visited[*it]=true;
            DFS(i+1,k+1);  //递归从第i+1个红点去找匹配
            visited[*it]=false;  //将递归前的访问到蓝点变成未访问
            Stack.pop();
          }
        }
      }
      if(k==Red.size()) {  //所有红点都已经找到匹配
        perfectMatch=true;
        int j;
        for(j=0;j<k;j++) {
          tempStack.push(Stack.top());
          Stack.pop();
        }
        weight=0;
        for(j=0;j<k;j++) {
          pair<int,int>p=tempStack.top();
          weight+=graph.connect[p.first][p.second];
          tempStack.pop();
          Stack.push(p);
        } 
        pair<stack<pair<int,int> >,int>p(Stack,weight);
        MatchArray.push_back(p);
      }
    }
};

void main() {
  Bipartite_Graph<string>bg(0,1);  //不带权值的无向图
  bg.show();
//  bg.Hungary();
  bg.OptimalMatch();
  
}

测试：

一：不是二部图的图

二 存在孤立点的二部图

三：存在最优匹配的二部图