匈牙利演算法代碼

① 運行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;
}