锐客网

  1. 首页 > it技术 > >

匈牙利算法c++代码

首先说几个定义。以下定义是我自己用通俗的语言说的，以便于不太了解图论的同学也能够有个大概的认识。
二分图：有点资料也叫作二部图。它是如果一个图可以分为两个子集X和Y，且X和Y通过有边连接。通俗点说，就是X的每一个边的另一个端点只能是Y里的一个顶点，Y的每个边的另一个端点只能是X的一个顶点。
最大匹配：在二分图中，最大匹配包含的边（连接X中顶点x和Y中顶点y的边）是所有匹配中边数最多的。
完全匹配：在二分图中，有一个连接X和Y的匹配，（现在主要关注X），如果X中所有的顶点都在Y中有对应的匹配，而不管Y中是否所有的点都在X中是否有匹配，我们把这样的匹配叫作（从X到Y的）完全匹配，也叫作饱和X的匹配。完全匹配需要|X|<=|Y|，就是需要X的顶点的个数少于Y的顶点的个数。
完美匹配：如果在二分图中，存在一个匹配，且有X和Y的个数相等，且该匹配对于X是完备的，对于Y也是完备的。通俗的说就是，X和Y的顶点是一一对应的。有的书或资料中也叫作完备匹配，总之就是perfect matching。
还有一点，我在学习这部分的误解。那就是，匈牙利算法所求出的是二分图（有点资料也叫作二部图）的最大匹配，而该最大匹配不一定是完备，所以也不一定是完美匹配。

匈牙利算法c++代码
文章图片

直接上代码
广度搜索（DFS）
特点：
优点，实现简洁，理解容易。适用：稠密图，由于边多，DFS找增广路很快。复杂度O（n3）

#include #include using namespace std; #define MAXN 10//MAXN表示X集合和Y集合顶点个数的最大值 int nx,ny; //x和y集合中顶点的个数 int g[MAXN][MAXN]; //邻接矩阵，g[i][j]为1表示有连接 int cx[MAXN],cy[MAXN]; //cx[i],表示最终求得的最大匹配中，与x集合中元素Xi匹配的集合Y中顶点的索引 //cy[i],表示最终求得的最大匹配中，与y集合中元素Yi匹配的集合X中顶点的索引//DFS算法中记录顶点访问状态的数据mk[i]=0表示未访问过，为1表示访问过 int mk[MAXN]; //从集合X中的定顶点u出发，用深度有限的策略寻找增广路 //这种增广路只能是当前的匹配数增加1 int path(int u){ for(int v=0; v "<

程序运行结果：
匈牙利算法c++代码
文章图片


深度搜索（BFS）
特点：适用稀疏的二分图，边少，增广路短。复杂度O(N3)

#include #include using namespace std; #defineMAXN 10 int nx=3,ny=4; int g[MAXN][MAXN]; int cx[MAXN]; int cy[MAXN]; int pred[MAXN]; int queue[MAXN]; int MaxMatch(){ int i,j,y; int cur,tail; int res=0; memset(cx,-1,sizeof(cx)); memset(cy,-1,sizeof(cx)); for(i=0; i-1){ cx[cy[pred[y]]]=y; cy[y]=cy[pred[y]]; y=pred[y]; } cy[y]=i; cx[i]=y; res++; } return res; }int main() { g[0][0]=0; g[0][1]=1; g[0][2]=1; g[0][3]=0; g[1][0]=0; g[1][1]=1; g[1][2]=0; g[1][3]=0; g[2][0]=1; g[2][1]=0; g[2][2]=1; g[2][3]=1; int num= MaxMatch(); cout<<"num="< "<

程序运行结果一样：
匈牙利算法c++代码
文章图片


【匈牙利算法c++代码】

    推荐阅读


    上一篇：与宝贝的两个故事

    下一篇：Boosting 25年（2014 周志华老师）报告笔记