图论matlab代码整理：二分图网络流最短路最小生成树

haidaowang · 发表于 2021-7-16 10:55

EDA365欢迎您登录！

您需要登录才可以下载或查看，没有帐号？注册

x

1.1 最大匹配

%图论二部图最大匹配匈牙利算法
m=5;%X中有5个元素
n=5;%Y中有5个元素
%横坐标表示X中的元素,列坐标表示Y中的元素,0代表非邻接,1代表邻接
A=[0,1,1,0,0;
1,1,0,1,1;
0,1,1,0,0;
0,1,1,0,0;
0,0,0,1,1];
M=zeros(m,n);%M表示匹配
%求初始匹配M
for i=1:m
for j=1:n
if A(i,j)==1
M(i,j)=1;
break;
end;
end
if M(i,j)==1
break;
end
end %获得仅含一条边的初始匹配
while 1
for i=1:m
x(i)=0;
end %将记录X中点的标号和标记*
for i=1:n
y(i)=0;
end %将记录Y中点的标号和标记*
%将X中M的所有非饱和点都给以标号0和标记*,程序中用n+1表示0标号,标号为负数时表示标记*
for i=1:m
pd=1; %寻找X中M的所有非饱和点
for j=1:n
if M(i,j)==1
pd=0;
end;
end
if pd==1
x(i)=-n-1;
end
end
pd=0;
while 1
xi=0;
%假如X中存在一个既有标号又有标记*的点,则任取X中一个既有标号又有标记*的点xi
for i=1:m
if x(i)<0
xi=i;
break;
end;
end
if xi==0
pd=1;
break;
end %假如X中所有有标号的点都已去掉了标记*, 算法终止
x(xi)=x(xi)*(-1);%去掉xi的标记*
k=1;
%对与xi邻接且尚未给标号的yj都给以标号i
for j=1:n
if A(xi,j)&&y(j)==0
y(j)=xi;
yy(k)=j;
k=k+1;
end;
end
if k>1
k=k-1;
for j=1:k
pdd=1;
for i=1:m
if M(i,yy(j))==1
x(i)=-yy(j);
pdd=0;
break;
end
end %将yj在M中与之邻接的点xk(即xkyj∈M),给以标号j和标记*
if pdd==1%如果yjM-非饱和之直接逆向返回
break;
end
end
if pdd==1
k=1;
j=yy(j);%yj不是M的饱和点
while 1
P(k,2)=j;
P(k,1)=y(j);
j=abs(x(y(j)));%任取M的一个非饱和点yj,逆向返回
if j==n+1
break;
end %找到X中标号为0的点时结束,获得M-增广路P
k=k+1;
end
for i=1:k
if M(P(i,1),P(i,2))==1
M(P(i,1),P(i,2))=0;%将匹配M 在增广路P中出现的边去掉
else
M(P(i,1),P(i,2))=1;
end
end %将增广路P中没有在匹配M中出现的边加入到匹配M中
break;
end
end
end
if pd==1
break;
end;
end %假如X中所有有标号的点都已去掉了标记*, 算法终止
M %显示最大匹配M/ }) H( v" V0 S& J2 @1 ?

1.2 最优匹配

clear all
%图论最优匹配问题Kuhn-Munkres算法
n=4;
A=[4,5,5,1;
2,2,4,6;
4,2,3,3;
5,0,2,1];
%标记
for i=1:n
L(i,1)=0;
L(i,2)=0;
end
for i=1:n
for j=1:n
if L(i,1)<A(i,j)
L(i,1)=A(i,j);
end %初始可行点标记L
M(i,j)=0;%匹配
end
end
for i=1:n
for j=1:n%生成子图Gl
if L(i,1)+L(j,2)==A(i,j)
Gl(i,j)=1;
else
Gl(i,j)=0;
end
end
end
%获得仅含Gl 的一条边的初始匹配M
ii=0;
jj=0;
for i=1:n
for j=1:n
if Gl(i,j)==1
ii=i;
jj=j;
break;
end
end
if ii>0
break;
end
end
M(ii,jj)=1;
for i=1:n
S(i)=0;
T(i)=0;
NlS(i)=0;
end
while 1
for i=1:n
k=1;
for j=1:n
if M(i,j)==1
k=0;
break;
end
end
if k==1
break
end
end
if k==0
break
end %获得最佳匹配M, 算法终止
S(1)=i;%S={xi}
jss=1;%记录S中的元素数目
jst=0;%记录T中元素数目
while 1
jsn=0;
for i=1:jss
for j=1:n
if Gl(S(i),j)==1
jsn=jsn+1;
NlS(jsn)=j; %NL(S)={v|u∈S,uv∈EL}
for k=1:jsn-1
if NlS(k)==j
jsn=jsn-1;
end
end
end
end
end
if jsn==jst
pd=1; %判断NL(S)=T?
for j=1:jsn
if NlS(j)~=T(j)
pd=0;
break;
end
end
end
if jsn==jst&pd==1%如果NL(S)=T, 计算al, Inf 为∞
al=Inf;
for i=1:jss
for j=1:n
pd=1;
for k=1:jst
if T(k)==j
pd=0;
break;
end
end
if pd==1&al>L(S(i),1)+L(j,2)-A(S(i),j)
al=L(S(i),1)+L(j,2)-A(S(i),j);
end
end
end
for i=1:jss
L(S(i),1)=L(S(i),1)-al;
end %调整可行点标记
for j=1:jst
L(T(j),2)=L(T(j),2)+al;
end %调整可行点标记
for i=1:n
for j=1:n %生成子图GL
if L(i,1)+L(j,2)==A(i,j)
Gl(i,j)=1;
else Gl(i,j)=0;
end
M(i,j)=0;
k=0;
end
end
ii=0;jj=0;
for i=1:n
for j=1:n
if Gl(i,j)==1
ii=i;
jj=j;
break;
end;
end
if ii>0
break;
end
end %获得仅含Gl 的一条边的初始匹配M
M(ii,jj)=1;
break
else %NL(S)≠T
for j=1:jsn
pd=1; %取y∈NL(S)\T
for k=1:jst
if T(k)==NlS(j)
pd=0;
break;
end
end
if pd==1
jj=j;
break;
end
end
pd=0; %判断y 是否为M的饱和点
for i=1:n
if M(i,NlS(jj))==1
pd=1;
ii=i;
break;
end
end
if pd==1
jss=jss+1;
S(jss)=ii;
jst=jst+1;
T(jst)=NlS(jj); %S=S∪{x}, T=T∪{y}
else %获得Gl 的一条M-增广路, 调整匹配M
for k=1:jst
M(S(k),T(k))=1;
M(S(k+1),T(k))=0;
end
if jst==0
k=0;
end
M(S(k+1),NlS(jj))=1;
break;
end
end
end
end
MaxZjpp=0;
for i=1:n
for j=1:n
if M(i,j)==1
MaxZjpp=MaxZjpp+A(i,j);
end
end
end
M %显示最佳匹配M
MaxZjpp %显示最佳匹配M的权, 程序结束2 v6 i! G2 E5 v; r6 q

2 网络流

2.1 最大流

clear all
%图论网络流最大流 Ford-Fulkerson标号算法
n=6;%六个顶点
%C为容量的邻接的矩阵
C=[0,16,20,0,0,0;
0,0,0,10,10,0;
0,0,0,6,6,0;
0,0,0,0,0,10;
0,0,0,0,0,16;
0,0,0,0,0,0];
f=zeros(n,n);%F为流,初始流为0流
while 1%大循环
%标号过程
%标号初始化
No=zeros(1,6);d=zeros(1,6);%No记录该点标号的获得点 d记录调整量
No(1)=n+1;d(1)=inf;%给发点Vs标号
while 1%标号循环
pd=0;
for i=1:n
for j=1:n
if No(i)~=0%选择一个已标号的点x
if No(j)==0%对于它的未标号邻接点y
if C(i,j)>0%当(x,y)是一条边时
if f(i,j)<C(i,j)%判断增广链条件
No(j)=i; %标号
d(j)=min([C(i,j)-f(i,j),d(i)]);
pd=1;
end
end
if C(j,i)>0%当(y,x)是一条边时
if f(j,i)>0%判断增广链条件
No(j)=-i; %标号
d(j)=min([f(j,i),d(i)]);
pd=1;
end
end
end
end
end
end
if No(n)==1%当Vt表上号时跳出标号循环
break;
end
if pd==0; %当无法标号时跳出标号循环
break;
end
end
if No(n)==0%当Vt无法表上号时跳出大循环此时已是最大流
break;
end
%调整过程
t=n;%t为正在调整的点
for i=1:n %调整循环
if No(t)>0%正向流入的增加
f(No(t),t)=f(No(t),t)+d(n);
end
if No(t)<0%反向流出的减小
f(t,abs(No(t)))=f(t,abs(No(t)))-d(n);
end
if abs(No(t))==1%如果下一个点为发点跳出调整循环
break;
else
t=abs(No(t));%继续调整上游点
end
end
end
f%显示最大流
wf=0;
for i=1:n
wf=f(1,i)+wf;
end
wf%显示最大流流量
No%显示最小割6 W- `, w" B8 j

2.2 最小费用最大流

clear all
%图论最小费用最大流问题程序
%最大流未知
%C为容量邻接矩阵
C=[0 8 7 0 0 0;
0 0 5 9 0 0;
0 0 0 0 9 0;
0 0 2 0 0 5;
0 0 0 6 0 10;
0 0 0 0 0 0];
%B为费用邻接矩阵
B=[0 2 8 0 0 0;
0 0 5 2 0 0;
0 0 0 0 3 0;
0 0 1 0 0 6;
0 0 0 4 0 7;
0 0 0 0 0 0];
n=6;%6个点
f=zeros(n,n);%初始流为0流
w=ones(n,n)*inf;%邻接矩阵初始化
while 1
%求最小费用流
%确定费用邻接矩阵
for i=1:6
for j=1:6
if i==j
w(i,j)=0;
end
if C(i,j)>0 %如果存在(i,j)这条边(路),再对w作出调整
if f(i,j)<C(i,j)
w(i,j)=B(i,j);
end
if f(i,j)==C(i,j)
w(i,j)=inf;
end
if f(i,j)>0
w(j,i)=-B(i,j);
end
if f(i,j)==0
w(j,i)=inf;
end
end
end
end
%使用Ford算法求最短路
[minroad,s]=Ford(w);
if minroad==inf%若不存在费用最短路,则已是最小费用最大流跳出循环
break;
end
%调整可行流
%记录最短路
t=n;
R=[n];
while 1
R=[R,s(t)];
if s(t)==1%找到最短路的初始点时跳出循环
break;
end
t=s(t);
end
%统计R中点数
for i=1:n
if R(i)==1
break;
end
end
number=i;%number为点数
%调整过程
%确定调整量
for j=number-1:-1:1
if C(R(j+1),R(j))>0%如果是正向边
r(j)=C(R(j+1),R(j))-f(R(j+1),R(j));
end
if C(R(j),R(j+1))>0%如果是负向边
r(j)=f(R(j),R(j+1));
end
end
dvt=min(r);%确定调整量
%调整
for j=number-1:-1:1
if C(R(j+1),R(j))>0%如果是正向边
f(R(j+1),R(j))=f(R(j+1),R(j))+dvt;
end
if C(R(j),R(j+1))>0%如果是负向边
f(R(j),R(j+1))=f(R(j),R(j+1))-dvt;
end
end
end
f %显示最小费用最大流
wf=0;
for i=1:n
wf=wf+f(1,i);
end
wf %显示流量
zwf=0;
for i=1:n
for j=1:n
zwf=zwf+f(i,j)*B(i,j);
end
end
zwf %显示费用
( [& v5 T6 p4 y* G8 n2 X

Ford.m

function [minroad,s]=Ford(w) %注意此文件名一定要为Ford.m
%图论最短路的Ford迭代算法
%w为邻接矩阵(点与点的关系)
n=size(w,1);%记录图中点数
%赋初值
for i=1:n
p(i)=inf;%V1到Vi的最短路长记为p(i)
s(i)=i;%V1到Vi的最短路中Vi的前一个点记为s(i)
end
p(1)=0;
s(1)=1;
while 1
pd=0;
for i=2:n
for j=1:n
if p(i)>p(j)+w(j,i) %如果到i还有更短的路
p(i)=p(j)+w(j,i); %修正p(i)
s(i)=j; %修正s(i)
pd=1;
end
end
end
if pd==0 %所有的p(i)都无变化终止循环
break;
end
end
minroad=p(n);$ K$ J3 f8 \6 D3 U' Q" h

3 最短路

3.1 Dijkstra

clear all
%图论最短路问题的Dijkstra算法
%邻接矩阵(点与点的关系)
w=[0,2,4,inf,inf,inf,inf;
2,0,inf,3,3,1,inf;
4,inf,0,2,3,1,inf;
inf,3,2,0,inf,inf,1;
inf,3,3,inf,0,inf,3;
inf,1,1,inf,inf,0,4;
inf,inf,inf,1,3,4,0];
n=size(w,1);%记录图中点数
for i=1:n
l(i)=w(1,i);%为l(v)赋初值
z(i)=1; %为z(v)赋初值1
end
s=[]; %s集合
s(1)=1; %s集合的第1个元素为起点
u=s(1);
k=1; %k记录集合s中点的数量
while k<n %当集合s未包含所有元素的时候执行循环
for i=1:n %更新一遍l(v),z(v)
if l(i)>l(u)+w(u,i)
l(i)=l(u);
z(i)=u;
end
end
%找l(i)中最小的v加入s集合
ll=l;
for i=1:n
for j=1:k
if i==s(j)
ll(i)=inf;%去除掉已经在s集合中的点
end
end
end
[lv,v]=min(ll);%求最小的l(v)
s(k+1)=v; %加入集合s
u=v;
k=k+1;
end
fprintf('最短路为:%1d->%1d->%1d->%1d\n',z(z(z(7))),z(z(7)),z(7),7)+ F8 C3 X# |$ _1 a" G- p: o% n0 n* y; _