建模-圖論學(xué)習(xí)報告保

矩 可達(dá)矩 Dijkstra算法（計算兩點(diǎn)間的最短路，l為源點(diǎn)，z為目的點(diǎn)，W為鄰接矩陣 floyd算法（計算任意兩點(diǎn)間的最短距離 pass2short.m(計算經(jīng)過某兩點(diǎn)的最短距離 版本 Euler圖和Hamilton Hamilton改良圈算法（找出比較好的Hamilton路 匹配問 Kuhn-Munkres算法（即賦權(quán)完備二元圖的最佳匹配程序 2F算法(Ford-Fulkerson算法)，求最大 參考文 矩可達(dá)矩描述圖中兩點(diǎn)是否有路徑相連，有則對應(yīng)值設(shè)為1，否則為0；計算方法為functionP=dgraf(A)for無向圖關(guān)聯(lián)矩陣和鄰接矩陣互1；functionW=incandadf(F,f)iff==0forforifF(i,j)~=0

elseiff==1fori=1:mfprint('Pleaseimputtherightvalueof有向圖關(guān)聯(lián)矩陣和鄰接矩陣互換算functionW=mattransf(F,f)iff==0forforifF(i,j)~=0W(j,k)=-

elseiff==1fori=1:mifF(a(1),i)==1fprint('Pleaseimputtherightvalueof最短路問的點(diǎn)，W為鄰接矩陣）算法思想1、初始化：將v1置為Pd(v1)=0,P={v1T=V-2、找最?。赫业骄哂凶钚≈档腡標(biāo)號的節(jié)點(diǎn)，若為vk，則將vkT改為P標(biāo)號P=P+{vk}，T=T-3、修改：修改與vk鄰的節(jié)點(diǎn)的T號值，若d(vk)+w(vk,vi)<d(vi)，4、重復(fù)2,3，直到vn改為P標(biāo)號function[l,z]=Dijkstra(W)n=size(W,1);fori=1whileforj=1ififfunctionfunction%%%returnsthedistance%returnsthedistanceandpathbetweenthestartnodeandtheend%%A:adjcent%s:start%e:end% %node %distance %pathvector %nodevisibility %sourcenodeisunvisible %parentnode%theshortestfori=1:n-1 %Sethasn-1nodesforj=1:niftemp=[temp(1:count)D(j)];temp=[temp(1:count)j=index;visit(j)=0;fork=1:nif%theshortestdistancepathifparent(e)==0 %pathprealllocationt=e;path(1)=t;count=1;whilet~=s&&t>0path=[ppath(1:count)];ififerror(['Thepathpreallocationlengthistooshort.',...'Pleaseredefinepathpreallocationparameter.']);floyd算法（計算任意兩點(diǎn)間的最短距離functionforforforforforif

Warshall-Floyd算法求任意兩點(diǎn)間的最短路基本思想設(shè)A=(aij 為賦權(quán)圖G=(V,E,F)的矩陣,當(dāng)vivj∈E時aij=F(vivj),否則取=+∞(i≠j),dijvivj點(diǎn)的距離,rijvi到vj點(diǎn)的最短路中一個點(diǎn)的編號①賦初值.i,j,dijaij,rijjk1.dij,rij.ij,dikdkj＜dij,dij=dikdkjrijk,=0,③終止判斷.dii＜0,vi的負(fù)回路,終止;k=n終止;否k=k+1,轉(zhuǎn)向②.最短路線可由rij得到n=8;A=[0281InfInfInf206Inf1InfInf86075121Inf70InfInf9Inf15Inf03InfInfInf1Inf304InfInf29Inf40InfInfInfInf8630];%中,Inf表示∞D(zhuǎn)=A;%賦初值for(i=1:n)for(j=1:n)R(i,j)=j;end;end%賦路徑初值if(D(i,k)+D(k,j)<D(i,j))D(i,j)=D(i,k)+D(k,jdijR(i,j)=k;end;end;end%rijkD%顯示每步迭代后的路長R%顯示每步迭代后的路徑pd=0;fori=1:n含有負(fù)權(quán)時if(D(i,i)<0)pd=1;break;end;endviend存在一條負(fù)回路,end 計算指定兩點(diǎn)間的最短距說明：W鄰接矩陣，k1，k2所指定的兩點(diǎn)標(biāo)號。function[Pu]=n2short(W,k1,k2)whileforforif

whilekk~=k1forV(1,i)=U(k1,kk)-ifV(1,i)==U(k1,i)

forj=length(wrow):-1:1n1short.m(計算某點(diǎn)到其它所有點(diǎn)的最短距離說明：功能思想類似于dijstra算法，只是源點(diǎn)可以設(shè)定，輸出所有最短距離function[PmD]=n1short(W,k)fori=1:n[Pd]=n2short(W,k,i);pass2short.m(計算經(jīng)過某兩點(diǎn)的最短距離說明：當(dāng)你已知源點(diǎn)和目的點(diǎn)后，條件為必須經(jīng)過某兩點(diǎn)，可以用以下算法解決。k2為源點(diǎn)和目的點(diǎn)，t1，t2，為所必需經(jīng)過的點(diǎn)。需要調(diào)用n2short算法基本思想為：調(diào)用算法三次，算k1t1，t1t2，t2k2三段路徑，再將它們拼function[Pd]=pass2short(W,k1,k2,t1,t2)[p1d1]=n2short(W,k1,t1);[p2[p3d3]=n2short(W,t2,k2);[p4[p5d5]=n2short(W,t2,t1);[p6d6]=n2short(W,t1,k2);ifP=[p1p2(2:length(p2))p3(2:length(p3))];p=[p4p5(2:length(p5))最小生成最小生成樹的Kruskal算法（避圈法將圖G中的邊按權(quán)數(shù)從小到大逐條,按不構(gòu)成圈的原則加入到中(若有選擇時,不同的選擇可能會導(dǎo)致最后生成樹的權(quán)數(shù)不同),q(T)=p(G)1為止,T的邊數(shù)G的頂點(diǎn)數(shù)1為止版本function[Tc]=krusf(d,flag)ifnargin==1forforifd(i,j)~=0

fori=1:mifforj=1:nift(j)==tmax

ifa=[inf5060infinfinfinf;50infinf6540infinf;60infinf52infinfinf6552inf503042;inf40inf50inf70inf;infinfinf3070infinf;...infinf4542infinfinf];whilelength(result)~=length(a)-版本3（帶注釋Kruskal避圈法的程序代碼如下n=8;A=[0281000206010086075121070009030400290400000863k=1;記錄Afor(i=1:n-1)for(j=i+1:n)%此循環(huán)是查找Aif(A(i,j)>0)x(k)=A(i,j);%數(shù)組x記錄Akk=1;for(s=1:k-1)if(x(k)==x(s))kk=0;break;end;end%排除相同的正數(shù)k=k-1顯示Afor(i=1:k-1)for(j=i+1:k)%將xT(n,n)=0;%將矩陣T中所有的元素賦值為0q=0;%記錄加入到樹T中的邊數(shù)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);加入邊到樹TTT=T臨時記錄while(1)pd=1;%TTfor(z=1:n)if(TT(y,z)>0)kk=kk+1;zz=z;end;endTT中的樹枝if(kk==1)TT(y,zz)=0;TT(zz,y)=0;pd=0;end;end砍掉TT中的樹枝if(pd)break;end;end%TT中所有的樹枝pd=0;判斷TTif(pd)T(i,j)=0;T(j,i)=0;%假如TT中有圈elseT顯示近似最小生成樹T,最小生成樹的Prim算法（破圈法）1、在G中任意選一個節(jié)點(diǎn)v1，令2、在V-Vt選取與某個vi€Vt接的節(jié)點(diǎn)vj，使得邊（vi，vj）的權(quán)值最小，在另Vt=Vt+{vj}，Et=Et+{（vi，vj）}，k=k+1；3、重復(fù)步驟2，使得k=|V|；版本1function[Tc]=Primf(a)whilefori=1:liflistV(i)==1forj=1:liflistV(j)==0&

forg=1:e-1a(1,2)=50;a(1,3)=60;a(2,4)=65;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;whileifindex(1,flag)~=index(2,flag)EulerHamiltonFleury算法（在一個Euler圖中找出Euler環(huán)注：包括三個文件；fleuf1.m,edf.m,flecvexf.mfunction[Tc]=fleuf1(d)%EulerT=0,c=0forifmod(a(i),2)==1iffprintf('thereisnotexitEulerpath.\n')ifforii=1:length(t1)while[flagged]=edf(matr,eds,vexs,ed,tem);ifed(1,eds)~=0&forg=1:eds

function[flaged]=edf(matr,eds,vexs,ed,tem)for[dvexf]=flecvexf(matr,i,vexs,eds,ed,tem);iff==1ifed(:,i)=[vexs(1,i)dvex];function[dvexf]=flecvexf(matr,i,vexs,eds,ed,temp)iflength(edd)==1forkk=1:length(edd)ifsum(m1)==0ifkkk==length(edd)forforl2=1:edsifedd1(1:2,l1)==ed(1:2,l2)if

iftemp<=length(dvex1)elseiftemp>length(dvex1)&Hamilton改良圈算法（找出比較好的Hamilton路說明：Hamilton圖是具有回路的圖，所謂回路就是經(jīng)過圖中每個節(jié)點(diǎn)有且僅有function[Cd1]=%d表示權(quán)值矩%C表示算法最終找到的Hamilton圈%v=[5167;3784;4194;299;1854;450;2442;2538;1340;764;2262;1840;41holdon;plot(v(:,1),v(:,2),'*');%fortext(v(i,1)-1,v(i,2)-2,dot);%plot(v(:,1),v(:,2));%連線fori=1:nforj=1:nd(i,j)=sqrt((v(i,1)-v(j,1))^2+(v(i,2)-forifC=[linspace(1,n,n)1];fornnn=1:20ifforfori=1:(m-forj=(i+2):(m-1)fork=(i+1):j

elseifn<=3ifn<=2fprint('ItdoesnotexistHamiltoncircle.');fprint('Anycirlceistherightforholdplot(v(:,1),v(:,2),'*');%描點(diǎn)fori=1:ntext(v(i,1)-1,v(i,2)-2,dot);%匹配問較大基礎(chǔ)匹配算functionJ=matgraf(W)whilesum(sum(W))~=0ift1==0ifa(1)/n>floor(a(1)/n)

匈牙利算法（完美匹配算法說明主要用于解決0-1（指派問題4包括三個文件使用方法輸入矩陣a，然后輸入輸入矩陣a，然后輸入function[e,s]=fc01(a,flag)ifnargin==1iffori=1:m(1)b(i,:)=b(i,:)-forb(:,j)=b(:,j)-whiletotal~=m(1)function[e,total]=fc02(d)whilet~=0functionb=fc03(b,e)whilet~=0fori=1:n(1)fori=1:n(1)ifall(e(:,2)-

輸入矩陣a，然后輸入輸入矩陣a，然后輸入匈牙利算法的另一程序（帶注釋m=5;n=5;A=[011011010110011000011];for(i=1:m)for(j=1:n)if(A(i,j))M(i,j)=1;break;end;end%if(M(i,j))break;end;endMfor(i=1:m)x(i)=0;endX中點(diǎn)的標(biāo)號和標(biāo)記for(i=1:n)y(i)=0;endY中點(diǎn)的標(biāo)號和標(biāo)記*for(i=1:m)pd=1;%XM的所有非飽和點(diǎn)if(pd)x(i)=-n-1;end;endXM的所有非飽和點(diǎn)都給以標(biāo)號0和標(biāo)記*,程序n+1表0標(biāo)號,標(biāo)號為負(fù)數(shù)時表示標(biāo)記for(i=1:m)if(x(i)<0)xi=i;break;end;endX中存在一個既有標(biāo)號又有標(biāo)記*的點(diǎn),則任X中一個既有標(biāo)號又有標(biāo)記*if(xi==0)pd=1;break;endX中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記*,x(xi)=x(xi)*(-1);xi的標(biāo)記*for(j=1:n)if(A(xi,j)&y(j)==0)y(j)=xi;yy(k)=j;k=k+1;end;endxiyj都ifor(i=1:m)if(M(i,yy(j)))x(i)=-yy(j);pdd=0;break;end;end%yjMxkxkyj∈M),j和標(biāo)記*if(pdd)k=1;j=yy(j)%yjMwhile(1)P(k,2)=j;P(k,1)=y(j);j=abs(x(y(j)));%Myj,if(j==n+1)break;endX0的點(diǎn)時結(jié)束,獲得MPfor(i=1:k)if(M(P(i,1),P(i,2)))M(P(i,1),P(i,2))=0;%將匹配MPelseM(P(i,1),P(i,2))=1;end;endPMMif(pd)break;end;endX中所有有標(biāo)號的點(diǎn)都已去掉了標(biāo)記*,MM,Kuhn-Munkres（即賦權(quán)完備二元圖的最佳匹配程序說明：用于完備二元圖的最佳匹配輸入：圖的鄰接矩陣出：最佳匹配functionkk=kexingdian(A)%求賦權(quán)完備二元圖最佳匹配A=[4551;2246;4233;5021];%A為鄰接矩陣for(i=1:n)for(j=1:n)if(L(i,1)<A(i,j))L(i,1)=A(i,j);end;%初始可行點(diǎn)標(biāo)記for(i=1:n)for(j=1:n生成子圖GlelseGl(i,j)=0;end;end;endif(ii)break;end;end獲得僅含Gl的一條邊的初始匹配Mif(k==0)break;end獲得最佳匹配M,算法終 %S={xi},T=ffor(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} %判斷NL(S)=T?if(jsn==jst&pd)al=Inf;如果NL(S)=T,計算al,Inf為∞for(i=1:jss)L(S(i),1)=L(S(i),1)-al;end%調(diào)整可行點(diǎn)標(biāo)記for(j=1:jst)L(T(j),2)=L(T(j),2)+al;end調(diào)整可行點(diǎn)標(biāo)記for(i=1:n)for(j=1:n)%生成子圖GLelseGl(i,j)=0;endif(ii)break;end;end獲得僅含Gl的一條邊的初始匹配Melse%NL(S)≠T %y∈NL(S)\T %判斷y是否為M的飽和點(diǎn) %S=S∪{x},T=T∪{y}else%獲得Gl的一條M-增廣路,調(diào)整匹配MM%顯示最佳匹配MMaxZjpp顯示最佳匹配M的權(quán),程序結(jié)最小費(fèi)用最大2F算法(Ford-Fulkerson算法)，求最大u，v∈Vf(u,v)=00。在每次迭代st之間的都被找出來，根據(jù)最大流最小割定理，當(dāng)不包含增廣路徑時，fG中的一個最大流。輸入：容量（圖的鄰接矩陣）%C=[0430000;0000300003000002%0000004;00000000000000000]function[f%C表示容%f1表示當(dāng)前流量，默認(rèn)為%f表示最大%wf表示最大流的流ifnargin==1;while(1)whilefor(i=1:n)if(No(i))forif(No(j)==0&if(d(j)>d(i))elseif(No(j)==0&f(j,i)>0)if(d(j)>d(i))

if(No(n)|pd)ifwhile(1)elseif(No(t)<0)f(No(t),t)=f(No(t),t)-if(No(t)==1)for(i=1:n)

for(j=1:n)版本2（帶注釋Ford--Fulkersonn=8;C=[054300000005300000032000000200000000000000000000000000000];%for(i=1:n)for(j=1:n)f(i,j)=0;end;end%取初始可行流ffor(i=1:n)No(i)=0;d(i)=0;endNo,d圖6-No(1)=n+1;d(1)=Inf;%vs標(biāo)號while(1)pd=1;%標(biāo)號過程for(i=1:n)if(No(i))%vifor(j=1:n)if(No(j)==0&f(i,j)<C(i,j)vj,vivjNo(j)=i;d(j)=C(i,j)-elseif(No(j)==0&f(j,i)>0)%vj,當(dāng)vjviNo(j)=-if(No(n)|pd)break;end;end%vt得到標(biāo)號或者無法標(biāo)號,if(pd)break;end%vt未得到標(biāo)號,f已是最大流,dvt=d(n);t=n;進(jìn)入調(diào)整過程,dvtif(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%后向弧調(diào)整if(No(t)==1)for(i=1:n)No(i)=0;d(i)=0;end;break;end當(dāng)tvs時,終止調(diào)整過程t=No(t);end;end;%繼續(xù)調(diào)整前一段弧上的流fwf=0;for(j=1:n)wf=wf+f(1,j);end計算最大流量f%顯示最大流wfNo顯示標(biāo)號,由此可得最小割,Busacker-Gowan算法(求最大流最小費(fèi)用說明：最大流的最小費(fèi)用輸入：弧容量矩C弧上單位流量費(fèi)輸出：最大流最小費(fèi)用矩陣，最大流量，最小費(fèi)%C=[0151600;0001314;0110170;00008;0000%b=[04100;00061;02030;00002;0000%function[fwf%C表示弧容量矩%b表示弧上單位流量的費(fèi)%f表示最大流最小費(fèi)用矩%wf最大流%zwf表示最小費(fèi)用while(1)for(i=1:n)for(i=1:n)for(j=1:n)if(C(i,j)>0&elseif(C(i,j)>0&elseif(C(i,j)>0)a(j,i)=-

for(i=2:n)for(k=1:n)forforif

ifif(p(n)==inf)whi