求欧拉回路的Fleury算法.doc
一、 实验内容：判断图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=v0e1v1e2emvm(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,e2,ei= Fleury算法流程图三、 完整源程序#include <iostream.h>#include <stdio.h>#include <string.h>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;s<=n;s+) flags=0; if(degreei=1)return false; 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 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; /input cout<<"nt输入顶点数和边数:" cin>>n>>m;/n顶点数 m边数 memset(M , 0 , sizeof(M); for (i = 1; i <=n; i +) degreei=0; for (i = 0; i < m; i +) cout<<"ntt输入第"<<i+1<<"边的顶点:"cin>>s>>t; 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;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) /判断有无奇度点 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该图的一条欧拉回路："for(i=1;i<=m+1;i+) cout<<T.nodei<<" " else cout<<"nt该图不存在欧拉回路!n"
