求歐拉回路的Fleury算法(共5頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、 實(shí)驗(yàn)內(nèi)容：判斷圖G是否存在歐拉回路，若存在，輸出其中一條歐拉回路。否則，顯示無回路。二、 實(shí)驗(yàn)過程與結(jié)果1. 問題簡(jiǎn)介：通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖2. 算法思想（框圖）：（1）任取v0V(G)，令P0=v0.（2）設(shè)Pi=v0e1v1e2eivi已經(jīng)行遍，按下面方法來從E(G)-e1,e2,ei中選取ei+1：（a）ei+1與vi相關(guān)聯(lián)；（b）除非無別的邊可供行遍，否則ei+1不應(yīng)該為Gi=G-e1,e2,ei中的橋。（3）當(dāng)（2）不能再進(jìn)行時(shí)，算法停止。 可以證明，當(dāng)算法停止時(shí)所得簡(jiǎn)單

2、回路Pm=v0e1v1e2emvm(vm=v0)為G中一條歐拉回路。3. 數(shù)據(jù)輸入： 邊數(shù)5，點(diǎn)數(shù)6 相關(guān)聯(lián)的點(diǎn)1 2 1 3 2 5 4 2 3 2 4 54. 運(yùn)行結(jié)果：存在歐拉回路 1，3，2，4，5，2，15. 分析總結(jié)：Fleury算法是求歐拉圖的十分有效的算法，在執(zhí)行過程中需要用到類似于圖的深度優(yōu)先遍歷，因?yàn)樵撍惴ň褪切枰獙⒁颜业降穆窂讲粩嗟臄U(kuò)展下去，直到將所有邊擴(kuò)展進(jìn)路徑。判斷是否為歐拉圖（連通性和奇度點(diǎn)）圖 輸出無歐拉回路0=V0=1Pi=v0e1v1eivi,ei+1E(G)-e1,eiei+1與vi關(guān)聯(lián)，i=i+1,ei+1非橋Y輸出歐拉回路Pm=v0e1v1e2emvm(

3、vm=v0)E(G)-e1,e2,ei= Fleury算法流程圖三、 完整源程序?qū)Ｐ?專注-專業(yè)#include <iostream.h>#include <stdio.h>#include <string.h>struct stackint top , node81; T,F,A; /頂點(diǎn)的堆棧int M8181; /圖的鄰接矩陣int n;int degree81;bool brigde(int i,int j) int flag81,t,s; for(s=1;s<=n;s+) flags=0; if(degreei=1)return false;

4、 else Mij=0;Mji=0;A.top=1;A.node1=i;flagi=1;t=i;while(A.top>0) for(s=1;s<=n;s+) if(degrees>0) if(Mts=1) if(flags=0) A.top+; A.nodeA.top=s; flags=1;t=s;break; if(s>n) A.top-; t=A.nodeA.top; for(s=1;s<=n;s+) if(degrees>0) if(flags=0) Mij=Mij=1; return true; break; if(s>n) return f

5、alse; void Fleury(int x) /Fleury算法 int i,b=0; if(T.top<=n+1) T.top+;T.nodeT.top=x; for(i=1;i<=n;i+) if(Mxi=1)if(brigde(x,i)=false)b=1;break;if(b=1)Mxi=Mix=0;degreex-;degreei-;Fleury(i); void main() int m , s , t , num , i , j,flag81; /input cout<<"nt輸入頂點(diǎn)數(shù)和邊數(shù):" cin>>n>&

6、gt;m;/n頂點(diǎn)數(shù) m邊數(shù) memset(M , 0 , sizeof(M); for (i = 1; i <=n; i +) degreei=0; for (i = 0; i < m; i +) cout<<"ntt輸入第"<<i+1<<"邊的頂點(diǎn):"cin>>s>>t; Mst = 1; Mts = 1; degrees=degrees+1; degreet=degreet+1; /判斷是否存在歐拉回路for(i=1;i<=n;i+)flagi=0; s = 0;/判斷是

7、否連通F.top=1;F.node1=1;flag1=1;t=1;for(j=2;j<=n;j+)if(Mtj=1)F.top+;F.nodeF.top=j;flagj=1;t=j;break; if(j>n) s=1; else while(F.top<=n&&F.top>=1) for(j=2;j<=n;j+) if(Mtj=1) if(flagj=0) F.top+; F.nodeF.top=j; flagj=1;t=j;break; if(j>n) F.top-; t=F.nodeF.top; for(i=1;i<=n;i+) if(flagi=0) s=1; break; if(s=0) /判斷有無奇度點(diǎn) for (i = 1; i <= n; i +)num = 0;for (j = 1; j <= n; j +)num += Mij;if (num % 2 = 1) s +; break; if (s = 0) T.top=0;Fleury(1);cout<<"nt該