当前位置：文档视界 › 图论算法及其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中任意两点间的最短路.

图6-4

解：用Warshall-Floyd算法, MA TLAB程序代码如下：

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)

R(i,j)=R(k,j);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避圈法：将图G中的边按权数从小到大逐条考察, 按不构成圈的原则加入到T 中(若有选择时, 不同的选择可能会导致最后生成树的权数不同), 直到q (T ) = p (G ) - 1为止, 即T的边数= G的顶点数- 1为止.

Kruskal避圈法的MATLAB程序代码如下：

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; %临时变量

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)

T(n,n)=0; %将矩阵T中所有的元素赋值为0

q=0; %记录加入到树T中的边数

for(s=1:k)if(q==n)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; p d=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

T %显示近似最小生成树T, 程序结束

求二部图G的最大匹配的算法(匈牙利算法), 其基本思想是：从G的任意匹配M开始, 对X中所有M的非饱和点, 寻找M-增广路. 若不存在M-增广路, 则M为最大匹配; 若存在M-增广路P, 则将P中M与非M的边互换得到比M多一边的匹配M1 , 再对M1重复上述过程.

设G = ( X, Y, E )为二部图, 其中X = {x1, x2, … , x n }, Y = { y1, y2, … , y n}. 任取G的一初始匹配M (如任取e∈E, 则M = {e}是一个匹配).

①令S = φ , T = φ , 转向②.

②若M饱和X \ S的所有点, 则M是二部图G的最大匹配. 否则, 任取M的非饱和点u∈X \ S , 令S = S ∪{ u }, 转向③.

③记N (S ) = {v | u∈S, uv∈E}. 若N (S ) = T, 转向②. 否则取y∈N (S ) \ T. 若y是M 的饱和点, 转向④, 否则转向⑤.

④设x y∈M, 则令S = S ∪{ x }, T = T ∪{ y }, 转向③.

⑤u -y路是M-增广路, 设为P, 并令M = M⊕P, 转向①. 这里M⊕P = M∪P \ M∩P, 是对称差.

由于计算M-增广路P比较麻烦, 因此将迭代步骤改为：

①将X中M的所有非饱和点(不是M中某条边的端点)都给以标号0和标记*, 转向②.

②若X中所有有标号的点都已去掉了标记*, 则M是G的最大匹配. 否则任取X中一个既有标号又有标记*的点x i , 去掉x i的标记*, 转向③.

③找出在G中所有与x i邻接的点y j (即x i y j∈E ), 若所有这样的y j都已有标号, 则转向②, 否则转向④.

④对与x i邻接且尚未给标号的y j都给定标号i. 若所有的y j都是M的饱和点, 则转向⑤, 否则逆向返回. 即由其中M的任一个非饱和点y j的标号i找到x i, 再由x i的标号k找到y k , …, 最后由y t的标号s找到标号为0的x s时结束, 获得M-增广路x s y t…x i y j, 记P = {x s y t, …, x i y j }, 重新记M为M⊕P, 转向①.

⑤将y j在M中与之邻接的点x k (即x k y j∈M), 给以标号j和标记*, 转向②.

例1求图6-9中所示的二部图G的最大匹配.

图6-9

匈牙利算法的MATLAB程序代码如下：

m=5;n=5;A=[0 1 1 0 0

1 1 0 1 1

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

利用可行点标记求最佳匹配的算法步骤如下：

设G = ( X , Y , E , F )为完备的二部赋权图, L 是其一个初始可行点标记, 通常取

0)(},|)(max{)(Y y X x y L Y y xy F x L ∈∈???=∈= M 是G L 的一个匹配. ① 若X 的每个点都是M 的饱和点, 则M 是最佳匹配. 否则取M 的非饱和点u ∈X , 令S = {u }, T = φ , 转向②.

② 记N L (S ) = {v | u ∈S , uv ∈E L }. 若N L ( S ) = T , 则G L 没有完美匹配, 转向③. 否则转向④.

③ 调整可行点标记, 计算

a L = min { L ( x ) + L ( y ) - F (x y ) | x ∈S , y ∈Y \T }.

由此得新的可行顶点标记

H (v ) =,,),(,)(,)(T v S v v L a v L a v L L L ∈∈??

???+-

令L = H , G L = G H , 重新给出G L 的一个匹配M , 转向①.

④ 取y ∈N L ( S ) \T , 若y 是M 的饱和点, 转向⑤. 否则, 转向⑥.

⑤ 设x y ∈M , 则令S = S ∪{ x }, T = T ∪{ y }, 转向②.

⑥ 在G L 中的u - y 路是M -增广路, 记为P , 并令 M = M ⊕P , 转向①.

利用可行点标记求最佳匹配算法的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的权, 程序结束

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

⑴标号过程

①给发点v s以标号(+, +∞) , δs = +∞.

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

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

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

③重复②直到收点v t被标号或不再有点可标号时为止. 若v t得到标号, 说明存在一条可增广链, 转⑵调整过程; 若v t未得到标号, 标号过程已无法进行时, 说明f已经是最大流.

⑵调整过程

④决定调整量δ =δvt , 令u = v t.

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

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

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

例1求图6-19所示网络的最大流.

图6-19

利用Ford--Fulkerson标号法求最大流算法的MATLAB程序代码如下：

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记录标号

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)

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 %显示标号, 由此可得最小割, 程序结束

设网络G = ( V , E , C ), 取初始可行流 f 为零流, 求解最小费用流问题的迭代步骤： ① 构造有向赋权图 G f = ( V , E f , F ), 对于任意的v i v j ∈E , E f , F 的定义如下：

当f ij = 0时, v i v j ∈E f , F ( v i v j ) = b ij ;

当f ij = C ij 时, v j v i ∈E f , F ( v j v i ) = -b ij ;

当0＜ f ij ＜C ij 时, v i v j ∈E f , F ( v i v j ) = b ij , v j v i ∈E f , F ( v j v i ) = -b ij .

转向②.

② 求出有向赋权图G f = (V , E f , F )中发点v s 到收点v t 的最短路μ , 若最短路μ存在转向③; 否则f 是所求的最小费用最大流, 停止.

③ 增流. 同求最大流的方法一样, 重述如下：

令.,,

,-+∈∈?????-=μμδj i j i ij ij ij ij v v v v f f C δ = min {δ ij | v i v j ∈μ}, 重新定义流f = { f ij }为 f ij =,,,,-+∈∈?????-+μμδδj i j i ij

ij ij v v v v f f f

如果W f 大于或等于预定的流量值, 则适当减少δ 值, 使W f 等于预定的流量值, 那么 f 是所求的最小费用流, 停止; 否则转向①.

求解含有负权的有向赋权图G = ( V , E , F )中某一点到其它各点最短路的Ford 算法. 当v i v j ∈E 时记w ij = F (v i v j ), 否则取w ii =0, w ij = +∞(i ≠j ). v 1到v i 的最短路长记为π ( i ), v 1到v i 的最短路中v i 的前一个点记为θ ( i ). Ford 算法的迭代步骤：

① 赋初值π (1) = 0, π ( i ) = +∞, θ ( i ) = i , i = 2, 3, … , n .

② 更新π ( i ), θ ( i ). 对于i = 2, 3, … , n 和j = 1, 2, … , n , 如果π ( i )＜π ( j ) + w ji , 则令

π ( i ) = π ( j ) , θ ( i ) = j .

③ 终止判断：若所有的π ( i )都无变化, 停止; 否则转向②.

在算法的每一步中, π ( i )都是从v 1到v i 的最短路长度的上界. 若不存在负长回路, 则从v 1到v i 的最短路长度是π ( i )的下界, 经过n -1次迭代后π ( i )将保持不变. 若在第n 次迭代后π ( i )仍在变化时, 说明存在负长回路.

其它.

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

图6-22

求最小费用最大流算法的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 %显示最小费用最大流

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)

(图论)matlab模板程序

第一讲：图论模型程序一：可达矩阵算法 %根据邻接矩阵A（有向图）求可达矩阵P（有向图） function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; %将不为0的元素变为1 P; 程序二：无向图关联矩阵和邻接矩阵互换算法F表示所给出的图的相应矩阵 W表示程序运行结束后的结果 f=0表示把邻接矩阵转换为关联矩阵 f=1表示把关联矩阵转换为邻接矩阵 %无向图的关联矩阵和邻接矩阵的相互转换 function W=incandadf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F))/2; %计算图的边数 n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; %给边的始点赋值为1 W(j,k)=1; %给边的终点赋值为1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; %存在边，则邻接矩阵的对应值为1 W(a(2),a(1))=1;

end else fprint('Please imput the right value of f'); end W; 程序三：有向图关联矩阵和邻接矩阵互换算法 %有向图的关联矩阵和邻接矩阵的转换 function W=mattransf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 %由i发出的边，有向边的始点 W(i,k)=1; %关联矩阵始点值为1 W(j,k)=-1; %关联矩阵终点值为-1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); %有向边的两个顶点 if F(a(1),i)==1 W(a(1),a(2))=1; %有向边由a(1)指向a(2) else W(a(2),a(1))=1; %有向边由a(2)指向a(1) end end else fprint('Please imput the right value of f'); end W;

图论算法及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)

图论与网络优化课程设计_Matlab实现

图论与网络优化课程设计四种基本网络（NCN、ER、WS、BA）的构造及其性质比较摘要：网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。通过运用Matlab软件和NodeXL网络分析软件，计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。关键字：最近邻耦合网络；ER随机网络；WS小世界网络；BA无标度网络；Matlab；NodeXL。

四种基本网络（NCN、ER、WS、BA）的构造及其性质比较 1.概述 1.网络科学的概述网络科学（Network Science）是专门研究复杂网络系统的定性和定量规律的一门崭新的交叉科学，研究涉及到复杂网络的各种拓扑结构及其性质，与动力学特性（或功能）之间相互关系，包括时空斑图的涌现、动力学同步及其产生机制，网络上各种动力学行为和信息的传播、预测（搜索）与控制，以及工程实际所需的网络设计原理及其应用研究，其交叉研究内容十分广泛而丰富。网络科学中被广泛研究的基本网络主要有四种，即：规则网络之最近邻耦合网络（Nearest-neighbor coupled network）,本文中简称NCN；ER随机网络G(N,p)；WS小世界网络；BA无标度网络。本文着重研究这几种网络的构造算法程序。计算各种规模下（例如不同节点数、不同重连概率或者连边概率）各自的网络属性(包括边数、度分布、平均路径长度、聚类系数)，给出图、表和图示，并进行比较和分析。 2.最近邻耦合网络的概述如果在一个网络中，每一个节点只和它周围的邻居节点相连，那么就称该网络为最近邻耦合网络。这是一个得到大量研究的稀疏的规则网络模型。常见的一种具有周期边界条件的最近邻耦合网络包含围成一个环的N个节点，其中每K个邻居节点相连，这里K是一个偶数。这类网络的一个重要特征个节点都与它左右各/2 就是网络的拓扑结构是由节点之间的相对位置决定的，随着节点位置的变化网络拓扑结构也可能发生切换。 NCN的Matlab实现： %function b = ncn(N,K) %此函数生成一个有N个节点，每个节点与它左右各K/2个节点都相连的最近邻耦合网络 %返回结果b为该最近邻耦合网络对应的邻接矩阵 function b = ncn(N,K) b=zeros(N); for i = 1:N for j = (i+1):(i+K/2) if j<=N b(i,j)=1; b(j,i)=1; else b(i,j-N)=1;

(完整版)数字图像处理MATLAB程序【完整版】

第一部分数字图像处理

实验一图像的点运算实验1.1 直方图一．实验目的 1．熟悉matlab图像处理工具箱及直方图函数的使用； 2．理解和掌握直方图原理和方法；二．实验设备 1.PC机一台； 2.软件matlab。三．程序设计在matlab环境中，程序首先读取图像，然后调用直方图函数，设置相关参数，再输出处理后的图像。 I=imread('cameraman.tif');%读取图像 subplot(1,2,1),imshow(I) %输出图像 title('原始图像') %在原始图像中加标题 subplot(1,2,2),imhist(I) %输出原图直方图 title('原始图像直方图') %在原图直方图上加标题四．实验步骤 1. 启动matlab 双击桌面matlab图标启动matlab环境； 2. 在matlab命令窗口中输入相应程序。书写程序时，首先读取图像，一般调用matlab自带的图像，如:cameraman图像；再调用相应的直方图函数，设置参数；最后输出处理后的图像； 3．浏览源程序并理解含义； 4．运行，观察显示结果； 5．结束运行，退出；五．实验结果观察图像matlab环境下的直方图分布。 (a)原始图像 (b)原始图像直方图六．实验报告要求 1、给出实验原理过程及实现代码； 2、输入一幅灰度图像，给出其灰度直方图结果，并进行灰度直方图分布原理分析。

实验1.2 灰度均衡一．实验目的 1．熟悉matlab图像处理工具箱中灰度均衡函数的使用； 2．理解和掌握灰度均衡原理和实现方法；二．实验设备 1.PC机一台； 2.软件matlab；三．程序设计在matlab环境中，程序首先读取图像，然后调用灰度均衡函数，设置相关参数，再输出处理后的图像。 I=imread('cameraman.tif');%读取图像 subplot(2,2,1),imshow(I) %输出图像 title('原始图像') %在原始图像中加标题 subplot(2,2,3),imhist(I) %输出原图直方图 title('原始图像直方图') %在原图直方图上加标题 a=histeq(I,256); %直方图均衡化，灰度级为256 subplot(2,2,2),imshow(a) %输出均衡化后图像 title('均衡化后图像') %在均衡化后图像中加标题 subplot(2,2,4),imhist(a) %输出均衡化后直方图 title('均衡化后图像直方图') %在均衡化后直方图上加标题四．实验步骤 1. 启动matlab 双击桌面matlab图标启动matlab环境； 2. 在matlab命令窗口中输入相应程序。书写程序时，首先读取图像，一般调用matlab自带的图像，如:cameraman图像；再调用相应的灰度均衡函数，设置参数；最后输出处理后的图像； 3．浏览源程序并理解含义； 4．运行，观察显示结果； 5．结束运行，退出；五．实验结果观察matlab环境下图像灰度均衡结果及直方图分布。 (a)原始图像 (b)均衡化后图像

多目标优化实例和matlab程序

NSGA-II 算法实例目前的多目标优化算法有很多, Kalyanmoy Deb 的带精英策略的快速非支配排序遗传算法(NSGA-II) 无疑是其中应用最为广泛也是最为成功的一种。本文用的算法是MATLAB 自带的函数gamultiobj ，该函数是基于NSGA-II 改进的一种多目标优化算法。一、数值例子多目标优化问题 424221********* 4224212212112 12min (,)10min (,)55..55 f x x x x x x x x x f x x x x x x x x x s t x =-++-=-++-≤≤??-≤≤? 二、 Matlab 文件 1．适应值函数m 文件： function y=f(x) y(1)=x(1)^4-10*x(1)^2+x(1)*x(2)+x(2)^4-x(1)^2*x(2)^2; y(2)=x(2)^4-x(1)^2*x(2)^2+x(1)^4+x(1)*x(2); 2．调用gamultiobj 函数，及参数设置： clear clc fitnessfcn=@f; %适应度函数句柄 nvars=2; %变量个数 lb=[-5,-5]; %下限 ub=[5,5]; %上限 A=[];b=[]; %线性不等式约束 Aeq=[];beq=[]; %线性等式约束 options=gaoptimset('paretoFraction',0.3,'populationsize',100,'generations',200,'stallGenLimit',200,'TolFun',1e-100,'PlotFcns',@gaplotpareto); % 最优个体系数paretoFraction 为0.3；种群大小populationsize 为100，最大进化代数generations 为200， % 停止代数stallGenLimit 为200，适应度函数偏差TolFun 设为1e-100，函数gaplotpareto ：绘制Pareto 前端 [x,fval]=gamultiobj(fitnessfcn,nvars,A,b,Aeq,beq,lb,ub,options)

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%计算最小费用

图论算法及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)

图论算法及其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中任意两点间的最短路. 图6-4 解：用Warshall-Floyd算法, MA TLAB程序代码如下： 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)

图论举例MATLAB

例1 某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ? ? ??? ? ? ? ? ?????????∞∞∞∞∞∞ 055252510550102025251001020402010015252015050102540500 用矩阵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

图论matlab程序

第一讲：图论模型程序一：可达矩阵算法 function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P; 程序二：关联矩阵和邻接矩阵互换算法 function W=incandadf(F,f) if f==0 m=sum(sum(F))/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W;

程序三：有向图关联矩阵和邻接矩阵互换算法 function W=mattransf(F,f) if f==0 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=-1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); if F(a(1),i)==1 W(a(1),a(2))=1; else W(a(2),a(1))=1; end end else fprint('Please imput the right value of f'); end W;

超全图论matlab程序

超全的图论程序关注微信公众号“超级数学建模”，教你做有料、有趣的数模人程序一：可达矩阵算法 function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P; 程序二：关联矩阵和邻接矩阵互换算法 function W=incandadf(F,f) if f==0 m=sum(sum(F))/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W;

图论最短路MATLAB程序

最短路法MATLAB 程序例1：某公司在六个城市621,,,c c c 中有分公司，从i c 到j c 的直接航程票价记在下述矩阵的),(j i 位置上。（∞表示无直接航路），请帮助该公司设计一张城市1c 到其它城市间的票价最便宜的路线图。 ??????????????????∞∞∞∞∞∞ 05525251055010202525100102040 2010015252015050102540500 用矩阵n n a ?（n 为顶点个数）存放各边权的邻接矩阵，行向量pb 、1index 、 2index 、d 分别用来存放P 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ? ??=顶点未标号当第顶点已标号当第i i i pb 01)(； )(2i index 存放始点到第i 点最短通路中第i 顶点前一顶点的序号； )(i d 存放由始点到第i 点最短通路的值。求第一个城市到其它城市的最短路径的Matlab 程序如下：程序一： clc,clear

a=zeros(6); %邻接矩阵初始化 a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25; a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a'; %将矩阵数据对称赋予矩阵 a(find(a==0))=inf; %找到0值并赋值为inf pb(1:length(a))=0;pb(1)=1;index1=1;index2=ones(1,length(a)); d(1:length(a))=inf;d(1)=0; temp=1; %最新的P标号的顶点 while sum(pb)

图论matlab程序大全

图论程序大全程序一：可达矩阵算法 function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; P; 程序二：关联矩阵和邻接矩阵互换算法function W=incandadf(F,f) if f==0 m=sum(sum(F))/2; n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=1;

k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W; 程序三：有向图关联矩阵和邻接矩阵互换算法 function W=mattransf(F,f) if f==0

m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; W(j,k)=-1; k=k+1; end end end elseif f==1 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); if F(a(1),i)==1 W(a(1),a(2))=1; else

(完整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)

图论程序算法大全

图论算法matlab实现求最小费用最大流算法的 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;en d 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 时, 终止调整过程

图论算法及其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]'];

常用离散信号MATLAB程序及波形

常用离散信号MATLAB 表示单位抽样序列 n=-10:10; x=[n==0]; stem(n,x); title('单位抽样信号'); xlabel('n');ylabel('x');grid on ; -10 -8 -6 -4 -2 02 4 6 8 10 00.10.20.30.40.50.60.70.80.91单位抽样信号 n x 延迟k=4个单位后的图像为： -10 -8 -6 -4 -2 02 4 6 8 10 00.10.20.30.40.50.60.70.80.91单位抽样信号 n x

单位阶跃信号 n=-5:10; x=[zeros(1,5),ones(1,11)]; stem(n,x,'m','p'); axis([-5,10,-0.5,1.5]); title('单位阶跃信号'); xlabel('n');ylabel('幅度') grid on ; -5 510 -0.50 0.5 1 1.5 单位阶跃信号 n 幅度矩形序列 n=-5:15; x=[zeros(1,5),ones(1,11),zeros(1,5)]; stem(n,x,'r','h') axis([-5,15,-0.5,1.5]); title('矩形序列'); xlabel('时间');ylabel('幅度') grid on ;

-5 51015 -0.50 0.5 1 1.5 矩形序列时间幅度正弦序列 n=-5:0.1:5; xn=2*sin(0.5*pi*n+pi/3); stem(n,xn) axis([-5,5,-3,3]); title('正弦序列'); xlabel('时间');ylabel('幅度'); grid on ; -5 -4-3-2-1 012345 -3-2 -1 1 2 3 正弦序列时间幅度

用matlab实现寻找最短路

用matlab寻找赋权图中的最短路中的应用 1引言图论是应用数学的一个分支，它的概念和结果来源都非常广泛，最早起源于一些数学游戏的难题研究，如欧拉所解决的格尼斯堡七桥问题，以及在民间广泛流传的一些游戏的难题，如迷宫问题，博弈问题等。这些古老的难题，吸引了很多学者的注意。 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博弈论以及计算机科学等各个领域的问题时，发挥出很大的作用。在实践中，图论已成为解决自然科学，工程技术，社会科学，军事等领域中许多问题的有力工具之一。最短路问题是图论理论中的经典问题，寻找最短路径就是在指定网络中两节点间找一条距离最小的路。 2 最短路 2.1 最短路的定义（short-path problem）对最短路问题的研究早在上个世纪60年代以前就卓有成效了，其中对赋权图()0 w≥的有效算法是由荷兰著名计算机专家E.W.Dijkstra在1959年首次提出的,该算法能ij 够解决两指定点间的最短路,也可以求解图G中一特定点到其它各顶点的最短路。后来海斯在Dijkstra算法的基础之上提出了海斯算法。但这两种算法都不能解决含有负权的图的最短路问题。因此由Ford提出了Ford算法,它能有效地解决含有负权的最短路问题。但在现实生 w≥的情况下选择Dijkstra算法。活中,我们所遇到的问题大都不含负权,所以我们在()0 ij 若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，它不仅可以直接应用于解决生产实际的许多问题，如管路铺设、线路安装、厂区布局和设备更新等，而且经常被作为一个基本的工具，用于解决其他的做优化问题。定义1：若图G=G（V，E）中个边[v i,v j]都赋有一个实数w ij ，则称这样的图G为