图论matlab程序汇总分享.pdf

"图论matlab程序汇总分享.pdf" 图论是计算机科学和数学中的一个重要领域，它研究图的结构和算法。Matlab是数学和计算机科学中常用的编程语言，图论matlab程序汇总分享.pdf文件提供了多种图论模型和算法的Matlab实现。 图论模型 图论模型是研究图的结构和性质的数学模型。它可以用来描述复杂系统中的关系和结构。图论模型有多种，包括有向图、无向图、加权图等。 可达矩阵算法 可达矩阵算法是一种计算图的可达矩阵的算法。可达矩阵是图的邻接矩阵的幂次方和。它可以用来计算图中的可达性。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; 关联矩阵和邻接矩阵互换算法 关联矩阵和邻接矩阵是图论中两个重要的矩阵。关联矩阵是图的邻接矩阵的转置矩阵，而邻接矩阵是图的邻接关系矩阵。Matlab代码： 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代码： 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代码： Dijkstra算法 Dijkstra算法是一种计算图中两点之间的最短路的算法。Matlab代码： function [l,z]=Dijkstra(W) n = size (W,1); for i = 1 :n l(i)=W(1,i); z(i)=0; end i=1; while i<=n for j =1 :n if l(i)>l(j)+W(j,i) l(i)=l(j)+W(j,i); z(i)=j-1; if j<i i=j-1; end end end i=i+1; end Floyd算法 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 r; 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); end end end end