当前位置：文档之家› 图论算法

图论算法

Dijkstra 算法：

用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量

pb 、1index 、2index 、d

分别用

来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量

?=顶点未标号当第顶点已标号

当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号；

)(i d 存放由始点到第i 点最短通路的值。

求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc; M=10000;

a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a';

pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)

d(tb)=min(d(tb),d(temp)+a(temp,tb)); tmpb=find(d(tb)==min(d(tb))); temp=tb(tmpb(1)); pb(temp)=1;

index1=[index1,temp];

index=index1(find(d(index1)==d(temp)-a(temp,index1))); if length(index)>=2 index=index(1); end

index2(temp)=index; end

d, index1, index2

%dijkstra 最短路算法通用程序，用于求从起始点s 到其它各点的最短路

%D 为赋权邻接矩阵，d 为s 到其它各点最短路径的长度，DD 记载了最短路径生成树 function [d,DD]=dijkstra_aiwa(D,s) [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0;

dd=zeros(1,m);

dd(1,s)=1;

y=s;

DD=zeros(m,m);

DD(y,y)=1;

counter=1;

while length(find(dd==1))

for i=1:m

if dd(i)==0

d(i)=min(d(i),d(y)+D(y,i)); end

end

ddd=inf;

for i=1:m

if dd(i)==0&&d(i)

ddd=d(i);

end

yy=find(d==ddd);

counter=counter+1;

DD(y,yy(1,1))=counter;

DD(yy(1,1),y)=counter;

y=yy(1,1);

dd(1,y)=1;

end

Floyd算法：

Matlab程序如下：

clear;

clc;

M=10000;

a(1,:)=[0,50,M,40,25,10];

a(2,:)=[zeros(1,2),15,20,M,25];

a(3,:)=[zeros(1,3),10,20,M];

a(4,:)=[zeros(1,4),10,25];

a(5,:)=[zeros(1,5),55];

a(6,:)=zeros(1,6);

b=a+a';path=zeros(length(b));

for k=1:6

for i=1:6

for j=1:6

if b(i,j)>b(i,k)+b(k,j)

b(i,j)=b(i,k)+b(k,j);

path(i,j)=k;

end end end end b, path

prim 算法构造最小生成树：

prim 算法如下：

（i ）}{1v P

=，Φ=Q ；

（ii ）while V

P =~

},,min(P V v P p w pv pv -∈∈=

}{v P P +=

}{pv Q Q +=

end

用prim 算法求右图的最小生成树。

用n result ?3的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab 程序如下： clc;clear; M=1000;

a(1,2)=50; a(1,3)=60; a(2,4)=65; a(2,5)=40; a(3,4)=52;a(3,7)=45;

a(4,5)=50; a(4,6)=30;a(4,7)=42; a(5,6)=70; a=[a;zeros(2,7)]; a=a+a';a(find(a==0))=M; result=[];p=1;tb=2:length(a); while length(result)~=length(a)-1 temp=a(p,tb);temp=temp(:); d=min(temp);

[jb,kb]=find(a(p,tb)==d); j=p(jb(1));k=tb(kb(1));

result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[]; end result

Kruskal 算法构造最小生成树：

我们用n index ?2存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号u 改记为此边的另一序号v ，同时把后面边中所有序号为u 的改记为v 。此方法的几何意义是：将序号u 的这个顶点收缩到v 顶点，u 顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收

缩掉，失去了被选取的资格。Matlab程序如下：

clc;clear;

M=1000;

a(1,2)=50; a(1,3)=60;

a(2,4)=65; a(2,5)=40;

a(3,4)=52;a(3,7)=45;

a(4,5)=50; a(4,6)=30;a(4,7)=42;

a(5,6)=70;

[i,j]=find((a~=0)&(a~=M));

b=a(find((a~=0)&(a~=M)));

data=[i';j';b'];index=data(1:2,:);

loop=max(size(a))-1;

result=[];

while length(result)

temp=min(data(3,:));

flag=find(data(3,:)==temp);

flag=flag(1);

v1=data(1,flag);v2=data(2,flag);

if index(1,flag)~=index(2,flag)

result=[result,data(:,flag)];

end

if v1>v2

index(find(index==v1))=v2;

else

index(find(index==v2))=v1;

end

data(:,flag)=[];

index(:,flag)=[];

end

result

构造Hamilton圈：

从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：

编写程序如下：

clc,clear

a(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;

a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;

a(3,4)=36;a(3,5)=68;a(3,6)=68;

a(4,5)=51;a(4,6)=61;

a(5,6)=13;

a(6,:)=0;

a=a+a';

c1=[5 1:4 6];

L=length(c1);

flag=1;

while flag>0

flag=0;

for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))

c1(m+1:n)=c1(n:-1:m+1);

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1));

end

circle=c1;

sum=sum1;

c1=[5 6 1:4];%改变初始圈，该算法的最后一个顶点不动

flag=1;

while flag>0

flag=0;

for m=1:L-3

for n=m+2:L-1

if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...

a(c1(m),c1(m+1))+a(c1(n),c1(n+1))

flag=1;

c1(m+1:n)=c1(n:-1:m+1);

end

sum1=0;

for i=1:L-1

sum1=sum1+a(c1(i),c1(i+1));

end

if sum1

sum=sum1;

circle=c1;

end

circle,sum

Ford-Fulkerso最大流算法：

从一个可行流f 开始, 求最大流的Ford--Fulkerson 标号算法的基本步骤：

⑴标号过程

①给发点vs 以标号(+, +∞) , d s = +∞.

②选择一个已标号的点x, 对于x 的所有未给标号的邻接点y, 按下列规则处理：

当yx∈E, 且f yx ＞0 时, 令d y = min { f yx , d x }, 并给y 以标号( x - , d y ).

当xy∈E, 且f xy＜C xy 时, 令d y = min {C xy - f xy , d x }, 并给y 以标号( x + , d y ).

③重复②直到收点vt 被标号或不再有点可标号时为止. 若vt 得到标号, 说明存在一条

可增广链, 转⑵调整过程; 若vt 未得到标号, 标号过程已无法进行时, 说明f 已经是最大流.

⑵调整过程

④决定调整量d =d vt , 令u = vt .

⑤若u 点标号为( v +, d u ), 则以f vu + d 代替 f vu ; 若u 点标号为( v -, d u ), 则以f vu - d

代替 f vu.

⑥若v = vs, 则去掉所有标号转⑴重新标号; 否则令u = v, 转⑤.

算法终止后, 令已有标号的点集为S, 则割集(S, S c )为最小割, 从而Wf = C (S, S c ).

用Ford-Fulkerson算法计算如下网络中的最大流，每条弧上的两个数字分别表示容量和当前流量。

编写程序如下：

clc,clear,M=1000;

u(1,2)=1;u(1,3)=1;u(1,4)=2;

u(2,3)=1;u(2,5)=2;

u(3,5)=1;

u(4,3)=3;u(4,5)=3;

f(1,2)=1;f(1,3)=0;f(1,4)=1;

f(2,3)=0;f(2,5)=1;

f(3,5)=1;

f(4,3)=1;f(4,5)=0;

n=length(u);

list=[];

maxf=zeros(1:n);maxf(n)=1;

while maxf(n)>0

maxf=zeros(1,n);pred=zeros(1,n);

list=1;record=list;maxf(1)=M;

while (~isempty(list))&(maxf(n)==0)

flag=list(1);list(1)=[];

index1=(find(u(flag,:)~=0));

label1=index1(find(u(flag,index1)...

-f(flag,index1)~=0));

label1=setdiff(label1,record);

list=union(list,label1);

pred(label1(find(pred(label1)==0)))=flag;

maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1));

record=union(record,label1);

label2=find(f(:,flag)~=0);

label2=label2';

label2=setdiff(label2,record);

list=union(list,label2);

pred(label2(find(pred(label2)==0)))=-flag;

maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2);

end

if maxf(n)>0

v2=n;

v1=pred(v2);

while v2~=1

if v1>0

f(v1,v2)=f(v1,v2)+maxf(n);

else

v1=abs(v1);

f(v2,v1)=f(v2,v1)-maxf(n);

end

v2=v1;

v1=pred(v2);

end

最大流通用程序

%function [f,s]=maxflow(startp,endp,c)

%c为容量网络

%对容量网络的填写做一下说明

%容量具有方向性，比如弧(i,j)的容量为10，弧(j,i)为0

%即矩阵无须有对称性

function [f,s]=maxflow(startp,endp,c)

n=length(c);

f=zeros(size(c));

l=zeros(1,n);d=zeros(1,n);examine=zeros(1,n);

l(startp)=0.5;d(startp)=inf;

while 1

ifexam=0;ifl=0;

for i=1:n

if l(i)~=0

ifl=ifl+1;

if examine(i)==1

ifexam=ifexam+1;

end

if ifl==ifexam

break;

end

for i=1:n

if l(i)~=0&examine(i)==0

break;

end

for j=1:n

if c(i,j)~=0

if f(i,j)

l(j)=i;

d(j)=min(d(i),c(i,j)-f(i,j)); end

end

if c(j,i)~=0

if f(j,i)>0&l(j)==0

l(j)=-i;

d(j)=min(d(i),f(i,j));

end

examine(i)=1;

if l(endp)~=0

j=endp;

while 1

if l(j)~=0.5

if l(j)>0

i=l(j);

f(i,j)=f(i,j)+d(endp);

j=i;

end

if l(j)<0

i=-l(j);

f(j,i)=f(j,i)-d(endp);

j=i;

end

else

l=zeros(1,n);break;

end

l(startp)=0.5;d(startp)=inf;examine=zeros(1,n);

end

s=[];ns=0;

for i=1:n

if l(i)~=0

ns=ns+1;

s(ns)=i;

end

fprintf('f为最大可行流\n');

fprintf('图的最小截划分得到的一个子集s为：\n');

disp(s);

匈牙利算法：

求图中所示的二部图G 的最大匹配. 匈牙利算法的MATLAB 程序代码如下：

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=5;n=5;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, 程序结束

最佳匹配算法：

利用可行点标记求最佳匹配算法的MATLAB 程序代码如下：

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)

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=

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的权, 程序结束

最小费用最大流算法：

在图6-22 所示运输网络上, 求s 到t 的最小费用最大流, 括号内为(Cij , bij ).

求最小费用最大流算法的MATLAB 程序代码如下：

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 %显示最小费用, 程序结束

图论算法及其MATLAB程序代码

图论算法及其MATLAB 程序代码求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法：设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%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)

图论算法详解(C++版)

1.1、prim算法: 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。【Prim算法思想】任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。【输出】连通所有城市的公路最小造价。【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】50 原图最小生成树 #include #include #include #include using namespace std; int i,j,k,n,m,mi,t,s,a[1000][1000]; void prim() { int mi,p,f,k,d[1000]; bool v[1000]; memset(v,false,sizeof(v)); f=1; for (i=2;i<=n;i++) {

d[i]=INT_MAX; } d[f]=0; s=0; for(i=1;i<=n;i++) { mi=INT_MAX; for (j=1;j<=n;j++) if ((v[j]==false) && (d[j]

图论算法及matlab程序的三个案例

图论实验三个案例单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②；实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma)

图论算法

Dijkstra 算法：用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量 pb 、1index 、2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ? ?=顶点未标号当第顶点已标号当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。求第一个城市到其它城市的最短路径的Matlab 程序如下： clear; clc; M=10000; a(1,:)=[0,50,M,40,25,10]; a(2,:)=[zeros(1,2),15,20,M,25]; a(3,:)=[zeros(1,3),10,20,M]; a(4,:)=[zeros(1,4),10,25]; a(5,:)=[zeros(1,5),55]; a(6,:)=zeros(1,6); a=a+a'; pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)=2 index=index(1); end index2(temp)=index; end d, index1, index2 %dijkstra 最短路算法通用程序，用于求从起始点s 到其它各点的最短路 %D 为赋权邻接矩阵，d 为s 到其它各点最短路径的长度，DD 记载了最短路径生成树 function [d,DD]=dijkstra_aiwa(D,s) [m,n]=size(D); d=inf.*ones(1,m); d(1,s)=0;

图论算法及matlab程序的三个案例

图论实验三个案例单源最短路径问题 1.1 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到 j v 的权 ij w =∞ 。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在1i v +，使1()min{()}i l v l v +=，v S ∈； ⑤ 1{}i S S v += ，1{}i S S v +=-，1i i =+，转②；实际上，Dijkstra 算法也是最优化原理的应用：如果121n n v v v v - 是从1v 到n v 的最短路径，则121n v v v - 也必然是从1v 到1n v -的最优路径。在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元素表示顶点i v 到 j v 的权 ij w ，若i v 到 j v 无边，则 realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数(1.7977e+308)。 function re=Dijkstra(ma)

maab图论程序算法大全

图论算法m a t l a b实现求最小费用最大流算法的 MATLAB 程序代码如下： 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;e nd 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 %后向弧调整量

matlab图论程序算法大全

精心整理图论算法matlab实现求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for 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 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif 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%计算最小费用

图论及其算法

《图论及其算法》 --最短路问题学院：通信学院姓名：周旋学号： S110131133 指导老师：陈六新

摘要图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这些图形通常用来描述某些事物之间的特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关系。通过对《图论及其应用》中最短路问题的深入学习，本文利用Dijkstra算法来解决日常生活中寻找最短路的问题。同时也是对本学期学习知识的巩固。关键词：最短路径 Dijkstra算法迭代

Abstract Graph theory is a branch of mathematics, it studies the object of picture. Graph theory graph is given by the number of points and lines connecting the two points of the graphic form. These graphics are often used to describe a specific relationship between certain things. And with the point on behalf of things, with the line connecting the two points that have a corresponding relationship between two things. Through the "Graph Theory and Its Applications," in-depth study of the shortest path problem. In this paper, we use The Dijkstra's algorithm not only to solve everyday life to find the shortest path problem, but also for the consolidation of the semester to learn the knowledge. Keyword: shortest path Dijkstra's algorithm Iteration

算法图论

算法图论（Graph Theoretic Algorithms）第一部分：区间图、弦图、相似图、完美图本书英文版共29讲，第一部分共12讲，系译者学习的同时为备以后查阅复习之便作的翻译，内容基本忠实于原著，且大部分是直译，同时加入了译者的少许想法，并补上了少部分略去的证明过程（限于译者的水平只能证明一些力所能及的证明）。第1讲是概论导读；第2到10讲比较详细地介绍了区间图、弦图及其相关的性质、算法（包括证明）以及延伸内容，其中第7到9讲涉及相似图的一些内容，部分定理尚未证明；第11、12讲介绍完美图、相交图及其部分特例，侧重于介绍性，概念结论较多但证明较少，可以作为知识性的阅读。《尚为解决的问题》是译者翻译学习过程中遇到的一些不懂的问题，原文中未给出详细证明，而译者目前还无法自己证明的，这些在译文中将用粗括号扩出。各路高手如有知道方法的情与译者联系，不胜感激！复旦附中葛潇

第一讲、概论本讲对这门课程的主要议题进行了大致的介绍。 1．概念这门课程涉及了一些特殊的图以及这些图上某些已经得到改进及仍未解决的问题。为了解我们所说的内容，我们必须回顾一些特殊图中的概念、算法、复杂度分析及NP —HARD问题。在这门课中对些将不作深入，我们假设读者以对这些有所了解。 2．一些图的分类下面我们将给出这门课程中将涉及的一些图的形式。在以后的各讲中将进行深入的分析。 z区间图（Interval graphs）：如果一个图能用一些区间的intersection graph表示，那么这个图称为区间图。更准确地说，给定一系列区间，将其中每个区间看作一个顶点，两个顶点间有边，当且仅当这两个点所代表的区间相交。一个图是区间图，当且仅当它能通过以上方法构造出来。（见图1）图1：一些区间及它们所构成的区间图我们同时学习各种相关的图，例如弦图和完美图。这部分的主要参考是[Gol80]。 z树（Trees）：一个图是一颗树，当且仅当它是连通的，并且没有环。我们将同样学习有关的图，例如partial k-trees. 这部分的主要参考是[Bod93]。 z平面图（Planar graphs）：一个图如果能画在二维平面上，且各边没有交点，则该图称为平面图。注意每个树都是平面图，但反之却不一定。我们将同样学习有关的图，例如outer-planar graphs 和 series-parallel graphs（混联图）。这部分的主要参考是[NC88]。本课程中除特别说明，一般所指的图都是简单的、连通的，且至少有两个顶点（或是图有意义的最少顶点）。显然这不会影响大多数算法的适用性。同时，一般给出的图都是无向图，虽然有时我们为了设计算法人为地加上方向。 3．一些问题下面是我们将学习的一些问题，以及它们在一些特殊图上的复杂度。 z最大独立集（Maximum Independent Set）：这是著名的NP难题。但在区间图中，最大独立集问题能够在O（N＋M）时间内解决，同时在树上可以在线性时间内解决，但对于平面图这仍是NP难题。 z最大割(Maximum Cut)：图G＝（V，E）上的一个割将该图的顶点分成两个子集：V＝A＋B。更准确地说，给定一种顶点划分，一个割是哪些一个端点在A中，另一个在B 中的边组成的集合。最大割问题是寻找一种顶点划分方式，使得对应割集中的边数最多。同样也有最小割问题。最小割问题用最大流的方法可以在多项式时间内解决，但最大割问题是NP难题。但在平面图上最大割问题是多项式级的；在树上，最大割问题是平凡

图论算法实例

1、最优连线问题（最优连线问题）我国西部的SV地区共有1个城市（标记为1）和9个乡镇（标记为2--10）组成，该地区不久将用上天然气，其中城市1含有井源.现要设计一供气系统，使得从城市1到每个乡镇（2--10）都有一条管道相边，并且铺设的管子的量尽可能的少.图7-9给出了SV 地区的地理位置图，表7-7给出了城镇之间的距离. Lingo程序如下：model: data: n=10; enddata sets: cities/1..n/: F; roads(cities,cities)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10 /: D, P; endsets data: D= 6 5 3 6 9 7 5 11 9 1 8 7 5 4 10 5

9; enddata F(n)=0; @for(cities(i) | i #lt# n: F(i)=@min(roads(i,j): D(i,j)+F(j)); ); @for(roads(i,j): P(i,j)=@if(F(i) #eq# D(i,j)+F(j),1,0) ); end 结果： 2、任意两点间的最短路程问题：某公司在六个城市c1, …,c6中有分公司，从ci到cj的直接航程票价记在下述矩阵中的(i,j) 位置上。（∞表示无直接航路），请帮助该公司设计一张任意两城市间的票价最便宜的路线表。 0 50 ∞40 25 10 50 0 15 20 ∞25 ∞15 0 10 20 ∞ 25 ∞20 10 0 55 10 25 ∞25 55 0 Lingo程序如下：

图论中的概念及重要算法

图论中的概念及重要算法常州一中林厚从 chi、图论中的基本概念一、图的概念简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph= （V，E）, V是点（称为"顶点”）的非空有限集合，E是线（称为"边”）的集合，边一般用（V x，V y）表示，其中V x，V y属于V。图（A）共有 4 个顶点、5 条边，表示为：V={v i, V2, V3, V4}，E={（V i，V2），（V i，V3），（V i，V4），（V2，V3），（V2，V4）} 二、无向图和有向图如果边是没有方向的，称此图为“无向图” ，如图（A）和图（C）,用一对圆括号表示无向边，如图（A）中的边（V i，V2），显然（V x，▼『）和（V y，V x）是两条等价的边，所以在上面E 的集合中没有再出现边（V2，V i）。如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边＜V i，V2＞。把边＜v x，v y＞中V称为起点，v y称为终点。显然此时边w，V y＞与边＜V y，V x＞是不同的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。图（B）表示为：V={V i，V2，V3}，E={＜V i，V2＞，＜V i，V3＞，＜ V2，V3＞，＜V3，V2＞} 如果两个顶点U V之间有一条边相连，则称U V这两个顶点是关联的。三、带权图一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的图称为带权图，也称为网（络）。四、阶图中顶点的个数称为图的阶。图（A）、图（B）、图（C）的阶分别为4、3、5。五、度图中与某个顶点相关联的边的数目，称为该顶点的度。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。图（A）中顶点V i，V2是奇点，V3，V4是偶点。

图论算法-最大流算法和最大匹配算法

clc,clear,M=1000; c(1,2)=3;c(1,4)=3; c(2,3)=1;c(2,4)=20; c(3,6)=3; c(4,5)=10; c(5,1)=4;c(5,3)=2;c(5,6)=13; n=length(u); list=[]; maxf=zeros(1:n);maxf(n)=1; while maxf(n)>0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (~isempty(list))&(maxf(n)==0) flag=list(1);list(1)=[]; index1=(find(u(flag,:)~=0)); label1=index1(find(u(flag,index1)... -f(flag,index1)~=0)); label1=setdiff(label1,record); list=union(list,label1); pred(label1(find(pred(label1)==0)))=flag; maxf(label1)=min(maxf(flag),u(flag,label1)... -f(flag,label1)); record=union(record,label1); label2=find(f(:,flag)~=0); label2=label2'; label2=setdiff(label2,record); list=union(list,label2); pred(label2(find(pred(label2)==0)))=-flag; maxf(label2)=min(maxf(flag),f(label2,flag)); record=union(record,label2); end if maxf(n)>0 v2=n; v1=pred(v2); while v2~=1 if v1>0 f(v1,v2)=f(v1,v2)+maxf(n); else v1=abs(v1); f(v2,v1)=f(v2,v1)-maxf(n); end v2=v1; v1=pred(v2);

图论算法-求(有向)图中任意两点间所有路径

求（有向）图中任意两点间所有路径 1建图：图类中包括如下信息：顶点集合，邻接矩阵。节点类中包括如下信息：是否被访问过，节点的名称，从这个节点访问到下一个节点的集合图1 图2 2 算法思路 A 将始点设置为已访问，将其入栈

B 查看栈顶节点V在图中，有没有可以到达、且没有入栈、且没有从这个节点V 出发访问过的节点 C 如果有，则将找到的这个节点入栈 D 如果没有，则将节点V访问到下一个节点的集合中每个元素赋值为零，V出栈 E 当栈顶元素为终点时，设置终点没有被访问过，打印栈中元素，弹出栈顶节点 F 重复执行B – E,直到栈中元素为空 Java代码 1.package util; 2. 3.public class Graph { 4. 5.private Vertex vertexList[]; // list of vertices 6.private int adjMat[][]; // adjacency matrix 7. 8.private int nVerts; 9.private static int MAX_VERTS = 7; // n个点 10. 11.int i = 0; 12.int j = 0; 13. 14.public Vertex[] getVertexList() { 15.return vertexList; 16.} 17. 18.public int[][] getAdjMat() { 19.return adjMat; 20.} 21. 22.public int getN() { 23.return MAX_VERTS; 24.} 25. 26.public Graph(int index) { 27.adjMat = new int[MAX_VERTS][MAX_VERTS]; // 邻接矩阵 28.vertexList = new Vertex[MAX_VERTS]; // 顶点数组 29.nVerts = 0; 30. 31.for (i = 0; i < MAX_VERTS; i++) { 32.for (j = 0; j < MAX_VERTS; j++) {

(完整word版)图论算法及matlab程序的三个案例.docx

图论实验三个案例单源最短路径问题 1.1 Dijkstra算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合 S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合 S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记l (v) 为顶点 v 到源点 v1的最短距离，v i ,v j V ，若 (v i , v j ) E ，记 v i到 v j的权 w ij。 Dijkstra算法： ①S{ v 1 } , l (v 1 ) 0 ； v V { v 1 } , l (v) , i 1,S V { v1}； ②S ，停止，否则转③； ③l (v) min{ l (v), d (v j , v)} ， v j S ，v S ； ④存在v i 1，使l (v i 1) min{ l (v)}，v S； ⑤S S U { v i 1 } ， S S { v i 1 } ，i i 1，转②；实际上，Dijkstra算法也是最优化原理的应用：如果v 1 v 2 L v n 1 v n是从 v 1 到 v n的最短路径，则v 1 v 2 L v n 1也必然是从 v 1 到 v n 1的最优路径。实现代码中，我们用到了距离矩阵，矩阵第i 行第 j 行元在下面的 MATLAB 素表示顶点v i 到 v j的权 w ij，若 v i 到 v j无边，则 w ij realmax ，其中 realmax 是 MATLAB常量，表示最大的实数 (1.7977e+308) 。 function re=Dijkstra(ma)

算法学习：图论之二分图最小覆盖(顶点以及边的最小覆盖)

二分图最小覆盖的Konig定理及其证明点的最小覆盖二分图：顶点可以分类两个集合X和Y，所有的边关联在两个顶点中，恰好一个属于集合Ｘ，另一个属于集合Ｙ。最小覆盖：最小覆盖要求用最少的点（Ｘ集合或Ｙ集合的都行）让每条边都至少和其中一个点关联。可以证明：最少的点（即覆盖数）＝最大匹配数 Konig定理：二分图的最小顶点覆盖数等于最大匹配数。证明：为主便叙述，假设G分为左边X和右边Y两个互不相交的点集。。。。。。假设G经过匈牙利算法后找到一个最大匹配M，则可知G中再也找不到一条增广路径。标记右边未匹配边的顶点，并从右边未匹配边的顶点出发，按照边：未匹配->匹配->未匹配...，的原则标记途中经过的顶点，则最后一条经过的边必定为匹配边。重复上述过程，直到右边不再含有未匹配边的点。记得到的左边已标记的点和右边未标记的点为S，以下证明S即为所求的最小顶点集。 1。| S | == M

因为每个点都是某个匹配边的其中一个端点。如果右边的哪个点是没有匹配过的，那么它早就当成起点被标记了；如果左边的哪个点是没有匹配过的，那就走不到它那里去（否则就找到了一条完整的增广路）。而一个匹配边又不可能左端点是标记了的，同时右端点是没标记的（不然的话右边的点就可以经过这条边到达了）。因此，最后我们圈起来的点与匹配边一一对应。 2。S能覆盖Gxx所有的边。反证：如果最大匹配边的两个端点不能覆盖所有边，证明存在至少一条边的两个端点都不是最大匹配边的两个端点（根据覆盖的定义，每条边都至少和其中一个点关联），而这就得到了更大的覆盖，所以S能覆盖所有边！ 3。S是最小的覆盖。覆盖M条匹配边至少需要|S|来覆盖转自: http: .html# 边的最小覆盖在一个ＰＸＰ的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每每条路径就是一个弱连通子集．由上面可以得出：１.一个单独的顶点是一条路径；２．如果存在一路径p1,p2,......pk，其中p1为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．

图论算法及其Matlab程序

求单源最短路径的Dijkstra算法的Matlab程序 function [d index1 index2]=Dijkf(a) M=max(max(a)); pb(1:length(a))=0; pb(1)=1; index1=1; index2=ones(1,length(a)); d(1:length(a))=M;d(1)=0;temp=1; while sum(pb)=2 index=index(1); end index2(temp)=index; end d; index1; index2; 求任意两点间最短路的Floyd算法的Matlab程序 function [D,R]=floyd(a) n=size(a,1); 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)

end end end D;R ; 求Euler回路的Fleury算法的Matlab程序function [eu,cEu]=arEuler(E) eu=0; cEu=[]; ncV=arComp(E); if max(ncV)>1 return end n=max(max(E(:,1:2))); m=size(E,1); for i=1:n b(i)=0; for j=1:m if E(j,1)==i|E(j,2)==i b(i)=b(i)+1; end end end rp=rem(b,2); srp=sum(rp); switch srp case 0, eu=1; case 2, eu=0.5; otherwise, return end if srp==0 v1=1; else v1=find(rp); v1=v1(1); end vc=v1; m=size(E,1); E1=[E(:,1:2),[1:m]'];