《求欧拉回路的Fleury算法.doc》由会员分享，可在线阅读，更多相关《求欧拉回路的Fleury算法.doc（5页珍藏版）》请在三一文库上搜索。
1、一、 实验内容：判断图G是否存在欧拉回路，若存在，输出其中一条欧拉回路。否则，显示无回路。二、 实验过程与结果1. 问题简介：通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图2. 算法思想（框图）：（1）任取v0V(G)，令P0=v0.（2）设Pi=v0e1v1e2eivi已经行遍，按下面方法来从E(G)-e1,e2,ei中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-e1,e2,ei中的桥。（3）当（2）不能再进行时，算法停止。 可以证明，当算法停止时所得简单回路Pm=v0e1v1e2
2、emvm(vm=v0)为G中一条欧拉回路。3. 数据输入： 边数5，点数6 相关联的点1 2 1 3 2 5 4 2 3 2 4 54. 运行结果：存在欧拉回路 1，3，2，4，5，2，15. 分析总结：Fleury算法是求欧拉图的十分有效的算法，在执行过程中需要用到类似于图的深度优先遍历，因为该算法就是需要将已找到的路径不断的扩展下去，直到将所有边扩展进路径。判断是否为欧拉图（连通性和奇度点）图 输出无欧拉回路0=V0=1Pi=v0e1v1eivi,ei+1E(G)-e1,eiei+1与vi关联，i=i+1,ei+1非桥Y输出欧拉回路Pm=v0e1v1e2emvm(vm=v0)E(G)-e1
3、,e2,ei= Fleury算法流程图三、 完整源程序#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.top-; t=A.nodeA.top; for(s=1
4、;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 , num , i , j,flag81; /inpu
5、t coutnm;/n顶点数 m边数 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) T.top=0;Fleury(1);coutnt该图的一条欧拉回路：;for(i=1;i=m+1;i+) coutT.nodei ; else coutnt该图不存在欧拉回路!n;