求歐拉回路,Fleury算法的C語言實現(xiàn)

1、歐拉(Euler)通路/回路1、基本概念：(1) 定義歐拉通路(歐拉跡)一通過圖中每條邊一次且僅一次，并且過每一頂點的通路。歐拉回路(歐拉閉跡)一通過圖中每條邊一次且僅一次，并且過每一頂點的回路。歐拉圖一存在歐拉回路的圖。歐拉圖就是從一頂出發(fā)每條邊恰通過一次又能回到出發(fā)頂點的 那種圖，即不重復(fù)的行遍所有的邊再回到出發(fā)點。通路和回路一稱Vieie2enVj為一條從v,到巧且長度為n的通路，其中長度是指通路中邊的 條數(shù).稱起點和終點相同的通路為一條回路。簡單圖一不含平行邊和自回路的圖?；旌蠄D一既有有向邊，也有無向邊的圖平凡圖一僅有一個結(jié)點的圖完全圖一有n個結(jié)點的且每對結(jié)點都有邊相連的無向簡單圖，稱

2、為無向完全圖；有n個結(jié)點的且每對結(jié)點之間都有兩條方向相反的邊相連的有向簡單圖為有向完全圖。(2) 歐拉圖的特征：無向圖a) G有歐拉通路的充分必要條件為：G連通，G中只有兩個奇度頂點(它們分別是歐拉通路 的兩個端點)。b) G有歐拉回路(G為歐拉圖):G連通，G中均為偶度頂點。有向圖a) D有歐拉通路：D連通，除兩個頂點外，其余頂點的入度均等于出度，這兩個特殊的頂 點中，一個頂點的入度比出度大1,另一個頂點的入度比出度小1。b) D有歐拉回路(D為歐拉圖)：D連通，D中所有頂點的入度等于出度。一個有向圖是歐拉圖，當且僅當該圖所有頂點度數(shù)都是0。2、弗羅萊(Fleury)算法思想一解決歐拉回路F

3、leury 算法：任取 v0 £ V(G)，令 P0=v0;設(shè)Pi=v0e1v1e2 ei vi已經(jīng)行遍，按下面方法從中選取ei+1 :(a) ei+1與vi相關(guān)聯(lián)；(b) 除非無別的邊可供行遍，否則 ei+1不應(yīng)該為Gi=G-e1,e2,，ei中的橋(所謂橋是一條刪除后使連通圖不再連通的邊)；(c) 當(b)不能再進行時，算法停止?？梢宰C明，當算法停止時所得的簡單回路Wm=v0e1v1e2 - .emvm(vm=v0)為G中的一條歐拉回路，復(fù)雜度為 O(e*e)。3、歐拉算法C語言描述 如下為算法的圖示動態(tài)過程:4、歐拉算法的C實現(xiàn)#include "SqStack.h&

4、quot; /堆棧的常見操作#include "Queue.h"/隊列的常見操作 typedef int Graph200200;int v,e;void DFS(Graph &G ,SqStack &S,int x,int t)int k=0,i,m,a;Push(S,x);for(i=t;i<v;i+)if(Gix>0)k=1;Gix=0; /刪除此邊Gxi=0;DFS(G,S,i,0);break;/if,forif(k=0)Pop(S);GetTop(S,m);Gxm=1;Gmx=1;a=x+1;if(StackLength(S)!=e)

5、Pop(S);DFS(G,S,m,a);/ifelsePush(S,x);/if/DFSint BFSTest(Graph G)int a200,x,i,k=0;LinkQueue Q;InitQueue(Q);EnQueue(Q,0);for(i=0;i<v;i+)ai=0;a0=1;while(!QueueEmpty(Q)DeQueue(Q,x);for(i=0;i<v;i+)if(Gxi>0)if(ai!=1)ai=1;EnQueue(Q,i);/if/whilefor(i=0;i<v;i+)if(ai=0)k=1;break;if(k=1)return 0;el

6、sereturn 1;void Euler(Graph &G ,int x)int m;SqStack S;InitStack(S);DFS(G,S,x,0);printf("該圖的一個歐拉回路為：");while(!StackEmpty(S)(GetTop(S,m);printf("->v%d”,m);Pop(S);/whilevoid InputM1(Graph &G)(int h,z;printf("Please input 頂點數(shù)和邊數(shù) n”);scanf("%d”,&v);scanf("%d”,

7、&e);for(int i=0;i<v;i+)for(int j=0;j<v;j+)Gij=0;printf("please int the 鄰接矩陣的值(起點(數(shù)字)終點(數(shù)字)：n");for(int i=0;i<e;i+)(scanf("%d",&h);scanf("%d”,&z);Gh-1z-1=1;Gz-1h-1=1;/for/InputM1int main()(int i,j,sum,k=0;Graph G;InputM1(G);if(BFSTest(G)=0)(printf("該

8、圖不是連通圖!n");exit(0);/iffor(i=0;i<v;i+)(sum=0;for（j=0;j<v;j+）sum+=Gij;if（sum%2=1）（k=1;break;/if/forif（k=1） printf（"該圖不存在歐拉回路！n"）;elseEuler（G,0）;return 1;頂點數(shù)5,邊數(shù)為6相關(guān)聯(lián)的點1 21 32 54 23 24 5運行結(jié)果（略）5、小常識：歐拉算法的起由及一筆畫問題七橋問題：18世紀著名古典數(shù)學(xué)問題之一。在哥尼斯堡的一個公園里，有七座橋?qū)⑵?雷格爾河中兩個島及島與河岸連接起來（如圖）。問是否可能從這四塊陸地中任一塊出發(fā)，恰好通過每座橋一次，再回到起點？歐拉于1736年研究并解決了此問題，他把問題歸結(jié)為如下右圖的 '筆畫”問題，證明上述走法是不可能的。f一筆劃：L凡是由偶點組成的連通圖，一定可以一筆畫成。 畫時可以把任一偶點為起點，最后一定能以這個點為終點畫完此圖。2. 凡是只有兩個奇點的連通圖（其余都為偶點），一定可以一筆畫