数学建模社区-数学中国

标题: 这可是图论所有算法的matlab程序哦 [打印本页]

作者: yuleichengchen 时间: 2012-7-26 21:13
标题: 这可是图论所有算法的matlab程序哦
用Warshall-Floyd 算法, MATLAB 程序代码如下：
n=8;
A=[0  2  8  1  Inf  Inf  Inf  Inf
2  0  6  Inf  1  Inf  Inf  Inf
8  6  0  7  5  1  2  Inf
1  Inf  7  0  Inf  Inf  9  Inf
Inf  1  5  Inf  0  3  Inf  8
Inf  Inf  1  Inf  3  0  4  6
Inf  Inf  2  9  Inf  4  0  3
Inf  Inf  Inf  Inf  8  6  3  0]; % MATLAB中, Inf表示∞
D=A; %赋初值
for(i=1:n)
for(j=1:n)
R(i,j)=j;
end;
end  %赋路径初值
for(k=1:n)
for(i=1:n)
for(j=1:n)
if(D(i,k)+D(k,j)<D(i,j))
D(i,j)=D(i,k)+D(k,j); %更新dij
            R(i,j)=k;
end;
end;
end %更新rij
   k  %显示迭代步数
   D  %显示每步迭代后的路长
   R  %显示每步迭代后的路径
   pd=0;
for i=1:n  %含有负权时
if(D(i,i)<0)
pd=1;
break;
end;
end  %存在一条含有顶点vi的负回路
if(pd)
break;
end %存在一条负回路,  终止程序
end  %程序结束

Kruskal避圈法
n=8;
A=[0  2  8  1  0  0  0  0
2  0  6  0  1  0  0  0
8  6  0  7  5  1  2  0
1  0  7  0  0  0  9  0
0  1  5  0  0  3  0  8
0  0  1  0  3  0  4  6
0  0  2  9  0  4  0  3
0  0  0  0  8  6  3  0];
k=1; %记录A中不同正数的个数
for(i=1:n-1)
for(j=i+1:n) %此循环是查找A中所有不同的正数
         if(A(i,j)>0)
x(k)=A(i,j); %数组x记录A中不同的正数
            kk=1;  %临时变量 if(k>1)
            for(s=1:k-1)
if(x(k)==x(s))
kk=0;
break;
end;
end  %排除相同的正数
               k=k+kk;
end;
end;
end
k=k-1  %显示A中所有不同正数的个数
for(i=1:k-1)
for(j=i+1:k) %将x中不同的正数从小到大排序
      if(x(j)<x(i))
xx=x(j);
x(j)=x(i);
x(i)=xx;
end;
end;
end
T(n,n)=0;  %将矩阵T中所有的元素赋值为0
q=0; %记录加入到树T中的边数
for(s=1:k)
if(q==n)             %q=n-1
break;
end  %获得最小生成树T, 算法终止
   for(i=1:n-1)
for(j=i+1:n)
if (A(i,j)==x(s))
T(i,j)=x(s);
T(j,i)=x(s); %加入边到树T中
               TT=T;  %临时记录T
               while(1)
pd=1;  %砍掉TT中所有的树枝
                  for(y=1:n)
kk=0;
                        for(z=1:n)
if(TT(y,z)>0)
kk=kk+1;
zz=z;
end;
end  %寻找TT中的树枝
                        if(kk==1)
TT(y,zz)=0;
TT(zz,y)=0;
pd=0;
end;
end  %砍掉TT中的树枝
                  if(pd)
break;
end;
end  %已砍掉了TT中所有的树枝
               pd=0;  %判断TT中是否有圈
               for(y=1:n-1)
for(z=y+1:n)
if(TT(y,z)>0)
pd=1;
break;
end;
end;
end
               if(pd)
T(i,j)=0;
T(j,i)=0; %假如TT中有圈
               else
q=q+1;
end;
end;
end;
end;
end
二匈牙利算法
m=5;
n=5;
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(m,n)=0;
for(i=1:m)
for(j=1:n)
if(A(i,j))
M(i,j)=1;
break;
end;
end %求初始匹配M
   if(M(i,j))
break;
end;
end  %获得仅含一条边的初始匹配M
while(1)
  for(i=1:m)
x(i)=0;
end  %将记录X中点的标号和标记*
  for(i=1:n)
y(i)=0;
end  %将记录Y中点的标号和标记*
  for(i=1:m)
pd=1; %寻找X中M的所有非饱和点
   for(j=1:n)
if(M(i,j))
pd=0;
end
end
   if(pd)
x(i)=-n-1;
end;
end  %将X中M的所有非饱和点都给以标号0和标记*, 程序中用n+1表
示0标号,  标号为负数时表示标记*
  pd=0;
  while(1)xi=0;
   for(i=1:m)
if(x(i)<0)
xi=i;
break;
end;
end %假如X中存在一个既有标号又有标记*的点,  则任
取X中一个既有标号又有标记*的点xi
if(xi==0)
pd=1;
break;
end  %假如X中所有有标号的点都已去掉了标记*, 算法终止
x(xi)=x(xi)*(-1); %去掉xi的标记*
k=1;
for(j=1:n)
if(A(xi,j)&y(j)==0)
y(j)=xi;
yy(k)=j;
k=k+1;
end;
end  %对与xi 邻接且尚未给标号的yj 都给以标号i
   if(k>1)
k=k-1;
      for(j=1:k)
pdd=1;
         for(i=1:m)
if(M(i,yy(j)))
x(i)=-yy(j);
pdd=0;
break;
end;
end  %将yj在M中与之邻接的点xk (即xkyj∈M), 给以标号j 和标记*

         if(pdd)
break;
end;
end
      if(pdd)
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)))
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)
break;
end;
end  %假如X中所有有标号的点都已去掉了标记*, 算法终止
M  %显示最大匹配M,  程序结束

可行点标记
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
ii=0;jj=0;
for(i=1:n)for(j=1:n)if(Gl(i,j))ii=i;jj=j;break;end;end
  if(ii)break;end;end  %获得仅含Gl的一条边的初始匹配M
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))k=0;break;end;end
if(k)break;end;end
  if(k==0)break;end  %获得最佳匹配M,  算法终止
  S(1)=i;jss=1;jst=0;  %S={xi}, T=f
  while(1)
jsn=0;
for(i=1:jss)for(j=1:n)if(Gl(S(i),j))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)al=Inf; %如果NL(S)=T, 计算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&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))ii=i;jj=j;break;end;end
      if(ii)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)jj=j;break;end;end
   pd=0;  %判断y是否为M的饱和点
   for(i=1:n)if(M(i,NlS(jj)))pd=1;ii=i;break;end;end
   if(pd)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))MaxZjpp=MaxZjpp+A(i,j);end;end;end
M  %显示最佳匹配M
MaxZjpp  %显示最佳匹配M的权,  程序结束

最大流的Ford--Fulkerson标号算法
n=8;C=[0  5  4  3  0  0  0  0
0  0  0  0  5  3  0  0
0  0  0  0  0  3  2  0
0  0  0  0  0  0  2  0
0  0  0  0  0  0  0  4
0  0  0  0  0  0  0  3
0  0  0  0  0  0  0  5
0  0  0  0  0  0  0  0];  %弧容量
for(i=1:n)for(j=1:n)f(i,j)=0;end;end  %取初始可行流f为零流
for(i=1:n)No(i)=0;d(i)=0;end  %No,d记录标号

图6-19
while(1)
  No(1)=n+1;d(1)=Inf; %给发点vs标号
  while(1)pd=1;  %标号过程
for(i=1:n)if(No(i))  %选择一个已标号的点vi
   for(j=1:n)if(No(j)==0&f(i,j)<C(i,j))  %对于未给标号的点vj, 当vivj为非饱和弧时
      No(j)=i;d(j)=C(i,j)-f(i,j);pd=0;
      if(d(j)>d(i))d(j)=d(i);end
      elseif(No(j)==0&f(j,i)>0)  %对于未给标号的点vj, 当vjvi为非零流弧时
      No(j)=-i;d(j)=f(j,i);pd=0;
      if(d(j)>d(i))d(j)=d(i);end;end;end;end;end
if(No(n)|pd)break;end;end %若收点vt得到标号或者无法标号,  终止标号过程
  if(pd)break;end %vt未得到标号, f 已是最大流,  算法终止
  dvt=d(n);t=n;  %进入调整过程, dvt 表示调整量
  while(1)
if(No(t)>0)f(No(t),t)=f(No(t),t)+dvt;  %前向弧调整
elseif(No(t)<0)f(No(t),t)=f(No(t),t)-dvt;end  %后向弧调整
if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0; end;break;end  %当t的标号为vs时,  终止调整过程
t=No(t);end;end;  %继续调整前一段弧上的流f
wf=0;for(j=1:n)wf=wf+f(1,j);end %计算最大流量
f  %显示最大流
wf  %显示最大流量
No  %显示标号,  由此可得最小割,  程序结束

解最小费用流问题的迭代

n=5;C=[0 15  16  0  0
0  0  0  13  14
0  11  0  17  0
0  0  0  0  8
0  0  0  0  0];  %弧容量
b=[0 4  1  0  0
0  0  0  6  1
0  2  0  3  0
0  0  0  0  2
0  0  0  0  0];  %弧上单位流量的费用
wf=0;wf0=Inf;  %wf表示最大流量, wf0 表示预定的流量值
for(i=1:n)for(j=1:n)f(i,j)=0;end;end  %取初始可行流f为零流
while(1)
  for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图
  for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j);
elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j);
elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end
  for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford算法求最短路,  赋初值
  for(k=1:n)pd=1; %求有向赋权图中vs到vt的最短路
for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end
if(pd)break;end;end  %求最短路的Ford算法结束
  if(p(n)==Inf)break;end  %不存在vs到vt的最短路,  算法终止.  注意在求最小费用最大流时构造有
向赋权图中不会含负权回路,  所以不会出现k=n
  dvt=Inf;t=n;  %进入调整过程, dvt 表示调整量
  while(1)  %计算调整量
if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t);  %前向弧调整量
elseif(a(s(t),t)<0)dvtt=f(t,s(t));end  %后向弧调整量
if(dvt>dvtt)dvt=dvtt;end
if(s(t)==1)break;end  %当t的标号为vs时,  终止计算调整量
t=s(t);end %继续调整前一段弧上的流f
  pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值
  t=n;while(1)  %调整过程
if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整
elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end  %后向弧调整
if(s(t)==1)break;end  %当t的标号为vs时,  终止调整过程
t=s(t);end
  if(pd)break;end %如果最大流量达到预定的流量值
  wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量
zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end %计算最小费用
f  %显示最小费用最大流

图6-22
wf  %显示最小费用最大流量
zwf  %显示最小费用,  程序结束

Dijkstra算法
function [min,path]=dijkstra(w,start,terminal)
n=size(w,1);
label(start)=0;
f(start)=start;
for i=1:n
if i~=start
   label(i)=inf;
end
end
s(1)=start;
u=start;
while length(s)<n
for i=1:n
      ins=0;
      for j=1:length(s)
         if i==s(j)
            ins=1;
         end,
end
      if ins==0
         v=i;
         if  label(v)>(label(u)+w(u,v))
               label(v)=(label(u)+w(u,v)); f(v)=u;
         end
end
end
v1=0;
   k=inf;
   for i=1:n
         ins=0;
         for j=1:length(s)
               if i==s(j)
                  ins=1;
               end
   end
            if ins==0
               v=i;
               if k>label(v)
                  k=label(v);
v1=v;
                  end
end
end
            s(length(s)+1)=v1;
            u=v1;
end
min=label(terminal); path(1)=terminal;
i=1;
while path(i)~=start
         path(i+1)=f(path(i));
         i=i+1 ;
end
   path(i)=start;
L=length(path);
path=path(L:-1:1);
Kruskal算法
b=[1 1 1 2 2 3 3 4;2 4 5 3 5 4 5 5;8 1 5 6 7 9 10 3];
[B,i]=sortrows(b',3);
B=B’;
m=size(b,2);
n=5;
t=1:n;
k=0;
T=[ ];
c=0;
for i=1:m
if t(B(1,i))~=t(B(2,i))
   k=k+1;
T(k,1:2)=B(1:2,i);
  c=c+B(3,i)
   tmin=min(t(B(1,i)),t(B(2,i)));
   tmax=max(t(B(1,i)),t(B(2,i)));
   for j=1:n
   if t(j)==tmax
      t(j)=tmin;
         end
   end
end
if k==n-1
   break ;
end
end

作者: yuleichengchen 时间: 2012-7-26 21:15
欢迎指教哦

作者: 寰宇 时间: 2012-7-27 08:58
恩恩，我看看。。

作者: 325 时间: 2012-8-6 16:54
有用，谢谢！！！

作者: Araneider 时间: 2012-8-16 10:01
应该有用的，谢谢分享。。。

作者: vjvj 时间: 2012-8-28 09:33
谢谢lz分享。。。。

作者: shaoxiagang 时间: 2012-9-4 17:03
不错啊，谢谢了

作者: ttliu_10 时间: 2013-1-21 14:45
挺好的，先留着

作者: 美赛参加者 时间: 2013-1-21 16:32
留着以后用

作者: lirui_Tshwdm 时间: 2013-1-24 11:22
充满乐趣的图论，无语中

作者: 苏晓萍 时间: 2013-1-28 19:58
非常有用，收藏了好好学习

作者: 黄雪玲 时间: 2013-1-30 20:36
太棒的程序了，可是下载不了也复制不了

作者: baiyanglalalala 时间: 2013-2-3 15:53

。。。。。。。。。。。。。。~~

作者: 唯世 时间: 2013-4-25 13:38
留着，以后有用

作者: 唯世 时间: 2013-4-25 13:40
bucuoou....................

作者: ruirui610 时间: 2013-7-15 17:49
楼主好人！楼下跟上！

作者: 李梦龙33 时间: 2013-8-10 19:16
haoren,好人

作者: 心玲丫 时间: 2013-9-8 15:00
留着看看……试试……

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)