匈牙利算法代码

① 运行C++程序时，提示.exe已停止工作 代码如下，是一个匈牙利算法的实现：

你已经定义了一个全局二维数组变量graph，在主函数中又定义了一个变量graph，这样冲突了，把主函数中的变量删除就OK了~~

② 关于二分图匹配的问题~

g:array[1..maxn,1..maxm]of boolean;
y:array[1..maxm]of boolean;
link:array[1..maxm]of longint;
function find(v:longint):boolean;
var i:longint;
begin
for i:=1 to m do
if g[v,i] and (not y[i]) then
begin
y[i]:=true;
if (link[i]=0)or find(link[i]) then
begin
link[i]:=v;
find:=true;
exit;
end;
end;
find:=false;
end;
begin
//read the graph into array g[][]
for i:=1 to n do
begin
fillchar(y,sizeof(y),0);
if find(i) then inc(ans);
end;
我用C++的,这个PASCAL程序是别处的
其中n,m分别为2部图两边节点的个数,两边的节点分别用1..n,1..m编号
g[x][y]=true表示x,y两个点之间有边相连
link[y]记录的是当前与y节点相连的x节点
y[i]记录的是y中的i节点是否被访问过.

算法的思路是不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条"交错轨",也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行"反色",容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路.
代码中find(i)就是寻找有没有从x点i开始的增广轨,如果有就进行上述操作,代码是递归的,所以看起来不是很显然,画个图试试就很清楚了.

P.S. 我比较笨,以前学习匈牙利算法时花了不少时间来理解这段代码的意思,希望楼主能很快理解,所以用很贫乏和不规范的语言描述了一下算法.希望能满意

③ 匈牙利算法百度里的一段代码是不是错了

他说的6个顶点,是指一个部分有6个顶点,两个部分一共就12个顶点了.
输入边的时候,1 2和2 1是不一样的,1 2是左边1点连右边2点,2 1是左边2点连右边1点.

④ 匈牙利算法 POJ 3041,要详细的解释，详细的！！！！

直接说，你要多少个字？

⑤ 急急急！！！寻匈牙利算法、KM算法的代码！

寻匈牙利算法:

function [result,msum]=sbppp(cost,m)
if nargin==1
dd=cost;
else
dd=max(max(cost))-cost;
end
[nop,nop]=size(cost);msum=0;
for i=1:nop
dd(i,:)=dd(i,:)-min(dd(i,:));
end
for j=1:nop
dd(:,j)=dd(:,j)-min(dd(:,j));
end
backup=dd;
for z=1:nop
bh=nop;bl=nop;result=[];
for k=1:nop
for i=1:nop
h=find(dd(i,:)==0);
if length(h)~=0&length(h)<bh
bh=length(h);
ch=i;
end
end
L=find(dd(ch,:)==0);
for j=1:length(L)
l=find(dd(:,L(j))==0);
if length(l)<bl
bl=length(l);
cl=L(j);
end
end
result(1,k)=ch;result(2,k)=cl;
dd(ch,:)=1;dd(:,cl)=1;
bl=nop;bh=nop;
if length(find(dd==0))==0
break
end
end
if length(result(1,:))==nop
break
end
dd=backup;DD=dd;d=zeros(nop);
for i=1:length(result(1,:))
d(result(1,i),result(2,i))=1;
end
D=~(d+dd);
p=[];q=[];k=1;zx=inf;
for i=1:nop
if sum(d(i,:))==0
p(k)=i;
k=k+1;
end
end
for j=1:length(p)
q=find(D(p(j),:)==1);
for e=1:length(q)
pp=find(d(:,q(e))==1);
if pp~=0
p(k)=pp;
k=k+1;
end
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
DD(:,q(u))=inf;
end
end
for l=1:length(p)
if min(DD(p(l),:))<zx
zx=min(DD(p(l),:));
end
end
for l=1:length(p)
q=find(D(p(l),:)==1);
for u=1:length(q)
dd(:,q(u))=dd(:,q(u))+zx;
end
end
for l=1:length(p)
dd(p(l),:)=dd(p(l),:)-zx;
end
backup=dd;
end
for i=1:length(result(1,:))
msum=msum+cost(result(1,i),result(2,i));
end

匈牙利算法的MatLab实现 收藏
程序文件 fenpei.m
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

function [z,ans]=fenpei(marix)

%//////////////////////////////////////////////////
%输入效率矩阵 marix 为方阵;
%若效率矩阵中有 M,则用一充分大的数代替;
%输出z为最优解，ans为 最优分配矩阵；
%//////////////////////////////////////////////////
a=marix;
b=a;
%确定矩阵维数
s=length(a);
%确定矩阵行最小值，进行行减
ml=min(a');
for i=1:s
a(i,:)=a(i,:)-ml(i);
end
%确定矩阵列最小值，进行列减
mr=min(a);
for j=1:s
a(:,j)=a(:,j)-mr(j);
end
% start working
num=0;
while(num~=s) %终止条件是“（0）”的个数与矩阵的维数相同
%index用以标记矩阵中的零元素，若a(i,j)=0，则index(i,j)=1,否则index(i,j)=0
index=ones(s);
index=a&index;
index=~index;
%flag用以标记划线位，flag=0 表示未被划线，
%flag=1 表示有划线过，flag=2 表示为两直线交点
%ans用以记录 a 中“（0）”的位置
%循环后重新初始化flag,ans
flag = zeros(s);
ans = zeros(s);
%一次循环划线全过程，终止条件是所有的零元素均被直线覆盖，
%即在flag>0位,index=0
while(sum(sum(index)))
%按行找出“（0）”所在位置，并对“（0）”所在列划线，
%即设置flag,同时修改index,将结果填入ans
for i=1:s
t=0;
l=0;
for j=1:s
if(flag(i,j)==0&&index(i,j)==1)
l=l+1;
t=j;
end
end
if(l==1)
flag(:,t)=flag(:,t)+1;
index(:,t)=0;
ans(i,t)=1;
end
end
%按列找出“（0）”所在位置，并对“（0）”所在行划线，
%即设置flag,同时修改index,将结果填入ans
for j=1:s
t=0;
r=0;
for i=1:s
if(flag(i,j)==0&&index(i,j)==1)
r=r+1;
t=i;
end
end
if(r==1)
flag(t,:)=flag(t,:)+1;
index(t,:)=0;
ans(t,j)=1;
end
end
end %对 while(sum(sum(index)))
%处理过程
%计数器：计算ans中1的个数，用num表示
num=sum(sum(ans));
% 判断是否可以终止，若可以则跳出循环
if(s==num)
break;
end
%否则，进行下一步处理
%确定未被划线的最小元素，用m表示
m=max(max(a));
for i=1:s
for j=1:s
if(flag(i,j)==0)
if(a(i,j)<m)
m=a(i,j);
end
end
end
end
%未被划线，即flag=0处减去m；线交点，即flag=2处加上m
for i=1:s
for j=1:s
if(flag(i,j)==0)
a(i,j)=a(i,j)-m;
end
if(flag(i,j)==2)
a(i,j)=a(i,j)+m;
end
end
end
end %对while(num~=s)
%计算最优（min）值
zm=ans.*b;
z=0;
z=sum(sum(zm));
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
运行实例：
>> a=[37.7 32.9 38.8 37 35.4
43.4 33.1 42.2 34.7 41.8
33.3 28.5 38.9 30.4 33.6
29.2 26.4 29.6 28.5 31.1
0 0 0 0 0];
>> [z,ans]=fenpei(a)

z =

127.8000

ans =

0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
1 0 0 0 0
0 0 1 0 0

⑥ 匈牙利算法网上下载的MATLAB程序（fenpei.m)为什么会出现死循环跪求答案！！

那估计是因为输入的新的数据不符合程序允许,或者超过极限值之类的吧

⑦ 求解试以下这个代码(就是匈牙利算法)

你去看网络的C代码吧
解释挺清楚的

⑧ 匈牙利算法 java

#include<stdio.h>
#include<string.h>
bool g[201][201];
int n,m,ans;
bool b[201];
int link[201];
bool init()
{
int _x,_y;
memset(g,0,sizeof(g));
memset(link,0,sizeof(link));
ans=0;
if(scanf("%d%d",&n,&m)==EOF)return false;
for(int i=1;i<=n;i++)
{
scanf("%d",&_x);
for(int j=0;j<_x;j++)
{
scanf("%d",&_y);
g[ i ][_y]=true;
}
}
return true;
}
bool find(int a)
{
for(int i=1;i<=m;i++)
{
if(g[a][ i ]==1&&!b[ i ])
{
b[ i ]=true;
if(link[ i ]==0||find(link[ i ]))
{
link[ i ]=a;
return true;
}
}
}
return false;
}
int main()
{
while(init())
{
for(int i=1;i<=n;i++)
{
memset(b,0,sizeof(b));
if(find(i))ans++;
}
printf("%d\n",ans);
}
}
Pascal:
Program matching;
Const
max = 1000;
Var
map : array [1..max, 1..max] of boolean; {邻接矩阵}
match: array [1..max] of integer; {记录当前连接方式}
chk : array [1..max] of boolean; {记录是否遍历过，防止死循环}
m, n, i, t1, t2, ans,k: integer;
Function dfs(p: integer): boolean;
var
i, t: integer;
begin
for i:=1 to k do
if map[p, i] and not chk[ i ] then
begin
chk[ i ] := true;
if (match[ i ] = 0) or dfs(match[ i ]) then {没有被连过 或 寻找到增广路}
begin
match[ i ] := p;
exit(true);
end;{if}
end;{for}
exit(false);
end;{function}
begin{main}
readln(n, m); {N 为二分图左侧点数 M为可连接的边总数}
fillchar(map, sizeof(map), 0);
k:=0;
for i:=1 to m do{initalize}
begin
readln(t1, t2);
map[t1, t2] := true;
if k<t2 then k:=t2;
end;{for}
fillchar(match, sizeof(match), 0);
ans := 0;
for i:=1 to n do
begin
fillchar(chk, sizeof(chk), 0);
if dfs(i) then inc(ans);
end;
writeln(ans);
for i:=1 to 1000 do
if match[ i ] <> 0 then
writeln(match[ i ], '-->', i);
end.

⑨ 如何通俗地解释匈牙利算法

是指二分图匹配的这个算法吧？下面是复制的，原文有图
原文地址：http://blog.csdn.net/lw277232240/article/details/72615522

二分图匹配，江湖称二分匹配，图论相关算法。

现在给出两个集合，我们拿约会来举例子。一方是男生集合，一方是女生集合，女生都比较内敛，对不认识的男孩纸并不喜欢一起约会，所以这里边就要有人际关系的问题了。

这里给男生编号n1,n2.....nn;女生编号v1v2....vn；

下面给出女生认识的男生的列表：
v1 :n1 ,n2.

v2 :n2, n3.

v3 : n1.

这里显而易见，1号男生2号男生是比较受欢迎的哈~。不用算法思想的去想这个问题我们可以这样思考：三号女生只认识1号男生，匹配上。（1组搞定）这个时候一号女生就不能选择1号男生了，她只能去选2号男生，这时候2号女生也就有了自己能选择的男生，这里我们就匹配成功了：

v1 n2

v2 n3

v3 n1

这里我们就完成了匹配的过程，这个时候我们因为所有人都有了约会对象，我们这个时候称之为最大匹配，同时也是完美匹配。

最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。刚刚给出的例子就是完美匹配。

那么我们要如何实现算法呢？因为代码是不能直接看出来如何匹配能得到最大匹配的，所以我们这里就要有一个顺序去寻找最大匹配，这里我们以编号大小的顺序来寻找约会对象。
从v1开始找，先找到了n1.约上，然后是v2,找到了n2,约上。v3找到了n1,但是这里n1和v1已经约好了，怎么办呢？v1对v3说：我还认识n2,我去问问他有没有约会人选，要是没有的话，n1让给你。（其实我想说她是傻逼。。。。）然后v1去找n2,但是n2和v2约上了，这个时候呢v2对v1说：我还认识n3,我去看看他有没有约会的人选，要是没有的话n2，让给你（这两个傻逼。。。。）然后v2找到了n3,n3乐的屁颠屁颠的，说正好没人约我，然后他俩约上了，v2找到了n3,那么v1就能和v2约上了，然后v3也就能和n1约上了，我们这个时候就从刚刚的两组匹配，转到了3组匹配。

刚刚所述的过程，其实就是在找增广路。（这里增广路的含义自己就可以理解了吧~）那么我们如何用代码实现这个过程呢？其实并不难，我们这里需要三个数组，一个是图，一个是询问vis标记，一个是match匹配。
出自：http://blog.csdn.net/lw277232240/article/details/72615522
原文有图

⑩ 求kM算法和匈牙利算法的程序代码

我学pascal的。本来我是有程序的。既然你要c的那我只好查给你了。问算法过程的话可以追问匈牙利算法1 #include<stdio.h>
2 #include<string.h>
3 bool g[201][201];
4 int n, m, ans;
5 bool b[201];
6 int link[201];
7 bool init()
8 {
9 int _x, _y;
10 memset(g, 0, sizeof(g));
11 memset(link, 0, sizeof(link));
12 ans = 0;
13 if (scanf("%d%d", &n, &m) == EOF)
14 return false;
15 for (int i = 1; i <= n; i++) {
16 scanf("%d", &_x);
17 for (int j = 0; j < _x; j++) {
18 scanf("%d", &_y);
19 g[i][_y] = true;
20 }
21 }
22 return true;
23 }
24
25 bool find(int a)
26 {
27 for (int i = 1; i <= m; i++) {
28 if (g[a][i] == 1 && !b[i]) {
29 b[i] = true;
30 if (link[i] == 0 || find(link[i])) {
31 link[i] = a;
32 return true;
33 }
34 }
35 }
36 return false;
37 }
38
39 int main()
40 {
41 while (init()) {
42 for (int i = 1; i <= n; i++) {
43 memset(b, 0, sizeof(b));
44 if (find(i))
45 ans++;
46 }
47 printf("%d\n", ans);
48 }
49 }KM算法#include <cstdio>
#include <memory.h>
#include <algorithm> // 使用其中的 min 函数
using namespace std;

const int MAX = 1024;

int n; // X 的大小
int weight [MAX] [MAX]; // X 到 Y 的映射（权重）
int lx [MAX], ly [MAX]; // 标号
bool sx [MAX], sy [MAX]; // 是否被搜索过
int match [MAX]; // Y(i) 与 X(match [i]) 匹配

// 初始化权重
void init (int size);
// 从 X(u) 寻找增广道路，找到则返回 true
bool path (int u);
// 参数 maxsum 为 true ，返回最大权匹配，否则最小权匹配
int bestmatch (bool maxsum = true);

void init (int size)
{
// 根据实际情况，添加代码以初始化
n = size;
for (int i = 0; i < n; i ++)
for (int j = 0; j < n; j ++)
scanf ("%d", &weight [i] [j]);
}

bool path (int u)
{
sx [u] = true;
for (int v = 0; v < n; v ++)
if (!sy [v] && lx[u] + ly [v] == weight [u] [v])
{
sy [v] = true;
if (match [v] == -1 || path (match [v]))
{
match [v] = u;
return true;
}
}
return false;
}

int bestmatch (bool maxsum)
{
int i, j;
if (!maxsum)
{
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
weight [i] [j] = -weight [i] [j];
}

// 初始化标号
for (i = 0; i < n; i ++)
{
lx [i] = -0x1FFFFFFF;
ly [i] = 0;
for (j = 0; j < n; j ++)
if (lx [i] < weight [i] [j])
lx [i] = weight [i] [j];
}

memset (match, -1, sizeof (match));
for (int u = 0; u < n; u ++)
while (1)
{
memset (sx, 0, sizeof (sx));
memset (sy, 0, sizeof (sy));
if (path (u))
break;

// 修改标号
int dx = 0x7FFFFFFF;
for (i = 0; i < n; i ++)
if (sx [i])
for (j = 0; j < n; j ++)
if(!sy [j])
dx = min (lx[i] + ly [j] - weight [i] [j], dx);
for (i = 0; i < n; i ++)
{
if (sx [i])
lx [i] -= dx;
if (sy [i])
ly [i] += dx;
}
}

int sum = 0;
for (i = 0; i < n; i ++)
sum += weight [match [i]] [i];

if (!maxsum)
{
sum = -sum;
for (i = 0; i < n; i ++)
for (j = 0; j < n; j ++)
weight [i] [j] = -weight [i] [j]; // 如果需要保持 weight [ ] [ ] 原来的值，这里需要将其还原
}
return sum;
}

int main()
{
int n;
scanf ("%d", &n);
init (n);
int cost = bestmatch (true);

printf ("%d ", cost);
for (int i = 0; i < n; i ++)
{
printf ("Y %d -> X %d ", i, match [i]);
}

return 0;
}