求欧拉回路的Fleury算法.doc

实验内容:判断图G是否存在欧拉回路,若存在,输出其中一条欧拉回路。否则,显示无回路。实验过程与结果问题简介:通过图(无向图或有向图)中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图算法思想(框图):(1)任取v0∈V(G),令P0=v0.(2)设Pi=v0e1v1e2…eivi已经行遍,按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1:(a)ei+1与vi相关联;(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的桥。(3)当(2)不能再进行时,算法停止。可以证明,当算法停止时所得简单回路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。数据输入:边数5,点数6 相关联的点12 13 25 42 32 45运行结果:存在欧拉回路1,3,2,4,5,2,1分析总结:Fleury算法是求欧拉图的十分有效的算法,在执行过程中需要用到类似于图的深度优先遍历,因为该算法就是需要将已找到的路径不断的扩展下去,直到将所有边扩展进路径。判断是否为欧拉图(连通性和奇度点)图 Gyn输出无欧拉回路P0=V0=1Pi=v0e1v1…eivi,ei+1∈E(G)-{e1,…,ei}ei+1与vi关联,i=i+1,ei+1非桥Y输出欧拉回路Pm=v0e1v1e2emvm(vm=v0)E(G)-{e1,e2,…,ei}=ΦFleury算法流程图完整源程序#include<>#include<>#include<>structstack{ inttop,node[81];}T,F,A;//顶点的堆栈intM[81][81];//图的邻接矩阵intn;intdegree[81];boolbrigde(inti,intj){ intflag[81],t,s;for(s=1;s<=n;s++)flag[s]=0;if(degree[i]==1) returnfalse;else{ M[i][j]=0;M[j][i]=0; =1; [1]=i; flag[i]=1; t=i; while(>0) { for(s=1;s<=n;s++) { if(degree[s]>0){ if(M[t][s]==1) if(flag[s]==0) { ++; []=s; flag[s]=1; t=s; break; } } } if(s>n){ --; t=[]; } } for(s=1;s<=n;s++) { if(degree[s]>0) if(flag[s]==0) { M[i][j]=M[i][j]=1; returntrue; break; } } if(s>n) returnfalse; }}voidFleury(intx)//Fleury算法{inti,b=0;if(<=n+1){++;[]=x;for(i=1;i<=n;i++)if(M[x][i]==1) if(brigde(x,i)==false) { b=1; break; } if(b==1) { M[x][i]=M[i][x]=0; degree[x]