什么是匈牙利算法?Hall定理是什么PASCAL语言还有HALL定理,

什么是匈牙利算法?Hall定理是什么
PASCAL语言
还有HALL定理,

谈匈牙利算法自然避不开Hall定理,即是：对于二部图G,存在一个匹配M,使得X的所有顶点关于M饱和的充要条件是：对于X的任意一个子集A,和A邻接的点集为T(A),恒有：│T(A)│ >= │A│
匈牙利算法是基于Hall定理中充分性证明的思想,其基本步骤为：
1．任给初始匹配M；
2．若X已饱和则结束,否则进行第3步；
3．在X中找到一个非饱和顶点x0,作V1 ← {x0},V2 ← Φ；
4．若T(V1) = V2则因为无法匹配而停止,否则任选一点y ∈T(V1)\V2；
5．若y已饱和则转6,否则做一条从x0 →y的可增广道路P,M←M?E(P),转2；
6．由于y已饱和,所以M中有一条边(y,z),作 V1 ← V1 ∪{z},V2 ← V2 ∪ {y},转4；
设数组up[1..n] --- 标记二分图的上半部分的点.
down[1..n] --- 标记二分图的下半部分的点.
map[1..n,1..n] --- 表示二分图的上,下部分的点的关系.
True-相连,false---不相连.
over1[1..n],over2[1..n] 标记上下部分的已盖点.
use[1..n,1..n] - 表示该条边是否被覆盖 .
首先对读入数据进行处理 ,对于一条边(x,y) ,起点进集合up,终点进集合down.标记map中对应元素为true.
1.寻找up中一个未盖点 .
2.从该未盖点出发 ,搜索一条可行的路线 ,即由细边出发,由细边结束,且细粗交错的路线 .
3.若找到 ,则修改该路线上的点所对应的over1,over2,use的元素.重复步骤1.
4.统计use中已覆盖的边的条数total,总数n减去total即为问题的解.

匈牙利算法 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。
增广路的定义(也称增广轨或交错轨)：
若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
由增广路的定义可以推...

全部展开

匈牙利算法 求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的时间复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。
增广路的定义(也称增广轨或交错轨)：
若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
由增广路的定义可以推出下述三个结论：
1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
2－P经过取反操作可以得到一个更大的匹配M’。
3－M为G的最大匹配当且仅当不存在相对于M的增广路径。
用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出)
算法轮廓：
(1)置M为空
(2)找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
(3)重复(2)操作直到找不出增广路径为止
时间复杂度 邻接矩阵：最坏为O(n^3) 邻接表：O(nm)
空间复杂度 O(n^2) O(m+n)
程序清单：
#include
#include
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 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.

收起