有关二部图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*E-mail: 2363702560@qq.com*Date: 2012/10/11*/#ifndef GRAPH_H#define GRAPH_Hconst 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*E-mail: 2363702560@qq.com*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*E-mail: 2363702560@qq.com*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();}

测试：

一：不是二部图的图

二 存在孤立点的二部图

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