(圖論)matlab模板程序(已修改)
2025-05-26 22:20 本頁面
【正文】 第一講：圖論模型程序一：可達矩陣算法%根據(jù)鄰接矩陣A（有向圖）求可達矩陣P（有向圖）function P=dgraf(A)n=size(A,1)。P=A。for i=2:n P=P+A^i。endP(P~=0)=1。 %將不為0的元素變?yōu)?P。程序二：無向圖關聯(lián)矩陣和鄰接矩陣互換算法F表示所給出的圖的相應矩陣W表示程序運行結束后的結果f=0表示把鄰接矩陣轉換為關聯(lián)矩陣f=1表示把關聯(lián)矩陣轉換為鄰接矩陣%無向圖的關聯(lián)矩陣和鄰接矩陣的相互轉換function W=incandadf(F,f)if f==0 %鄰接矩陣轉換為關聯(lián)矩陣 m=sum(sum(F))/2。 %計算圖的邊數(shù) 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 endelseif f==1 %關聯(lián)矩陣轉換為鄰接矩陣 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。 endelse fprint(39。Please imput the right value of f39。)。endW。程序三：有向圖關聯(lián)矩陣和鄰接矩陣互換算法%有向圖的關聯(lián)矩陣和鄰接矩陣的轉換function W=mattransf(F,f)if f==0 %鄰接矩陣轉換為關聯(lián)矩陣 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發(fā)出的邊，有向邊的始點 W(i,k)=1。 %關聯(lián)矩陣始點值為1 W(j,k)=1。 %關聯(lián)矩陣終點值為1 k=k+1。 end end endelseif f==1 %關聯(lián)矩陣轉換為鄰接矩陣 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(39。Please imput the right value of f39。)。endW。第二講：最短路問題程序0：最短距離矩陣W表示圖的權值矩陣D表示圖的最短距離矩陣%連通圖中各項頂點間最短距離的計算function D=shortdf(W)%對于W(i,j),若兩頂點間存在弧，則為弧的權值，否則為inf；當i=j時W(i,j)=0n=length(W)。D=W。m=1。while m=nfor i=1:nfor j=1:n if D(i,j)D(i,m)+D(m,j) D(i,j)+ D(i,m)+D(m,j)。 %距離進行更新 endendendm=m+1。endD。程序一：Dijkstra算法（計算兩點間的最短路）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)=j1。 if ji i=j1。 end end end i=i+1。end程序二：floyd算法（計算任意兩點間的最短距離）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)。 r(i,j)=r(i,k)。 end end end end程序三： 計算指定兩點間的最短距離function [P u]=n2short(W,k1,k2)n=length(W)。U=W。m=1。while m=n for i=1:n for j=1:n
醫(yī)療健康相關推薦
鄂ICP備17016276號-1