资源描述：
《求欧拉回路的Fleury算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、实验内容：判断图G是否存在欧拉回路，若存在，输出其中一条欧拉回路。否则，显示无回路。二、实验过程与结果1.问题简介：通过图（无向图或有向图）中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图2.算法思想（框图）：（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=v0e
2、1v1e2…emvm(vm=v0)为G中一条欧拉回路。3.数据输入：边数5，点数6相关联的点1213254232454.运行结果：存在欧拉回路1，3，2，4，5，2，15.分析总结：Fleury算法是求欧拉图的十分有效的算法，在执行过程中需要用到类似于图的深度优先遍历，因为该算法就是需要将已找到的路径不断的扩展下去，直到将所有边扩展进路径。判断是否为欧拉图（连通性和奇度点）图 Ｇｙｎ输出无欧拉回路Ｐ0=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
3、,e2,…,ei}=ΦFleury算法流程图一、完整源程序#include#include#includestructstack{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;A.top=1;A.node[1
4、]=i;flag[i]=1;t=i;while(A.top>0){for(s=1;s<=n;s++){if(degree[s]>0){if(M[t][s]==1)if(flag[s]==0){A.top++;A.node[A.top]=s;flag[s]=1;t=s;break;}}}if(s>n){A.top--;t=A.node[A.top];}}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)/
5、/Fleury算法{inti,b=0;if(T.top<=n+1){T.top++;T.node[T.top]=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]--;degree[i]--;Fleury(i);}}}voidmain(){intm,s,t,num,i,j,flag[81];//inputcout<<"t输入顶点数和边数:";cin>>n>>m;//n顶点数m边数memset(M,0,sizeof(M));for(i=
6、1;i<=n;i++)degree[i]=0;for(i=0;i>s>>t;M[s][t]=1;M[t][s]=1;degree[s]=degree[s]+1;degree[t]=degree[t]+1;}//判断是否存在欧拉回路for(i=1;i<=n;i++)flag[i]=0;s=0;//判断是否连通F.top=1;F.node[1]=1;flag[1]=1;t=1;for(j=2;j<=n;j++){if(M[t][j]==1){F.top++;F.node[F.top]=j;flag[j]=1;t
7、=j;break;}}if(j>n)s=1;else{while(F.top<=n&&F.top>=1){for(j=2;j<=n;j++){if(M[t][j]==1)if(flag[j]==0){F.top++;F.node[F.top]=j;flag[j]=1;t=j;break;}}if(j>n){F.top--;t=F.node[F.top];}}for(i=1;i<=n;i++)if(
