求欧拉回路的Fleury算法

1、实验内容：判断图 G 是否存在欧拉回路，若存在，输出其中一条欧拉回路。否则，显示无回路。 实验过程与结果1.问题简介： 通过图 (无向图或有向图)中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。 具有欧拉回路的图称为欧拉图2.算法思想(框图) ：(1) 任取 v0 V(G)，令 PO=vO.(2) 设Pi=v0e1v1e2eivi已经行遍，按下面方法来从E(G)-e1,e2,ei中选取ei+1 : ( a) ei+1 与 vi 相关联；ei+1不应该为Gi=G-e1,e2,ei中的桥。(b )除非无别的边可供行遍，否则3)当( 2)不能再进行时，算法停止。可以证明，当算法停止时所得简单回路

2、Pm=v0e1v1e2 emvm(vm=vO)为 G 中一条欧拉回路。3.数据输入：边数 5，点数 6相关联的点4.运行结果：1 ，3，2，4， 5， 2，存在欧拉回路分析总结：Fleury 算法是求欧拉图的十分有效的算法，在执行过程中需要用到类似于图的深度优先遍历，因 为该算法就是需要将已找到的路径不断的扩展下去，直到将所有边扩展进路径。5.Fleury算法流程图完整源程序#include viostream.h#include vstdio.h#include vstring.hif(sn)A.top-; t=A.nodeA.to p;struct stackint top , node8

3、1; T,F,A; /顶点的堆栈 int M8181; /图的邻接矩阵 int n;int degree81;bool brigde(int i,int j) int flag81,t,s; for(s=1 ;s v=n; s+) flags=0;if(degreei=1) return false;elseMij=0;Mji=0; A.to p=1;A.node1=i; flagi=1; t=i; while(A.to p0) for(s=1;sv=n;s+)if(degrees0)if(Mts=1)if(flags=0)A.t op+; A.nodeA.to p=s; flags=1;t=

4、s; break; for(s=1;sv=n;s+) if(degrees0) if(flags=0) Mij=Mij=1; return true; break;if(sn)return false; void Fleury(int x) /Fleury 算法 int i,b=0;if(T.t op v=n+1)T.t op+;T.nodeT.top=x; for(i=1;iv=n;i+) if(Mx i=1) if(brigde(x,i)=false) b=1; break;if(b=1)M凶i=Mi x=0; degreex-; degreei-;Fleury(i);void main(

5、)int m , s , t , num , i , j,flag81; /inputcoutvvnt输入顶点数和边数 :; cinnm; /n顶点数 m边数 memset(M , 0 , sizeof(M);for (i = 1; i v=n; i +)degreei=0;for (i = 0; i v m; i +)coutvvntt 输入第vvi+1vv边的顶点:; cinst;Mst = 1; Mts = 1; degrees=degrees+1; degreet=degreet+1;/判断是否存在欧拉回路for(i=1;iv=n;i+) flagi=0;s = 0;F.to p=1;

6、F.node1=1; flag1=1; t=1;for(j=2;jv=n;j+) if(Mtj=1) F.to P+;F.nodeF.t op=j; flagj=1; t=j; break;判断是否连通if(jn)s=1;elsewhile(F.t op v=n&F.to p=1) for(j=2;jv=n;j+)if(Mtj=1)if(flagj=0) if(jn)F.to P+;F.nodeF.t op=j; flagj=1;t=j; break;F.t op-; t=F.nodeF.to p; for(i=1;iv=n;i+) if(flagi=0) s=1; break;if(s=0)for (i = 1; i v= n; i +) num = 0;for (j = 1; j v= n; j +) num += Mij;if (num % 2 = 1)判断有无奇度点s +; break;if (s =