求歐拉回路的Fleury算法

1、 求歐拉回路的Fleury算法一、 實驗內(nèi)容：判斷圖G是否存在歐拉回路，若存在，輸出其中一條歐拉回路。否則，顯示無回路。二、 實驗環(huán)境： vc+三、 實驗過程與結(jié)果1. 問題簡介：通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍所有頂點的回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖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)行時，算法停止。 可

2、以證明，當(dāng)算法停止時所得簡單回路Pm=v0e1v1e2emvm(vm=v0)為G中一條歐拉回路。判斷是否為歐拉圖（連通性和奇度點）圖 輸出無歐拉回路0=V0=1Pi=v0e1v1eivi,ei+1E(G)-e1,eiei+1與vi關(guān)聯(lián)，i=i+1,ei+1非橋Y輸出歐拉回路Pm=v0e1v1e2emvm(vm=v0)E(G)-e1,e2,ei= Fleury算法流程圖3. 數(shù)據(jù)輸入： 邊數(shù)5，點數(shù)6 相關(guān)聯(liá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í)行過程中需要用到類似

3、于圖的深度優(yōu)先遍歷，因為該算法就是需要將已找到的路徑不斷的擴(kuò)展下去，直到將所有邊擴(kuò)展進(jìn)路徑。四、 完整源程序#include #include #include struct stackint top , node81; T,F,A; /頂點的堆棧int M8181; /圖的鄰接矩陣int n;int degree81;bool brigde(int i,int j) int flag81,t,s; for(s=1;s0) for(s=1;s0) if(Mts=1) if(flags=0) A.top+; A.nodeA.top=s; flags=1;t=s;break; if(sn) A.t

4、op-; t=A.nodeA.top; for(s=1;s0) if(flags=0) Mij=Mij=1; return true; break; if(sn) return false; 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

5、, num , i , j,flag81; /input coutnm;/n頂點數(shù) m邊數(shù) memset(M , 0 , sizeof(M); for (i = 1; i =n; i +) degreei=0; for (i = 0; i m; i +) coutntt輸入第i+1st; Mst = 1; Mts = 1; degrees=degrees+1; degreet=degreet+1; /判斷是否存在歐拉回路for(i=1;i=n;i+)flagi=0; s = 0;/判斷是否連通F.top=1;F.node1=1;flag1=1;t=1;for(j=2;jn) s=1; else while(F.top=1) for(j=2;jn) F.top-; t=F.nodeF.top; for(i=1;i=n;i+) if(flagi=0) s=1; break; if(s=0) /判斷有無奇度點 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)