求欧拉回路的Fleury算法.doc
- 文档编号:585921
- 上传时间:2023-04-29
- 格式:DOC
- 页数:8
- 大小:47KB
求欧拉回路的Fleury算法.doc
《求欧拉回路的Fleury算法.doc》由会员分享,可在线阅读,更多相关《求欧拉回路的Fleury算法.doc(8页珍藏版)》请在冰点文库上搜索。
求欧拉回路的Fleury算法
一、实验内容:
判断图G是否存在欧拉回路,若存在,输出其中一条欧拉回路。
否则,显示无回路。
二、实验环境:
vc++
三、实验过程与结果
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=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。
判断是否为欧拉图
(连通性和奇度点)
图 G
y
n
输出无欧拉回路
P0=V0=1
Pi=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算法流程图
3.数据输入:
边数5,点数6
相关联的点12
13
25
42
32
45
4.运行结果:
存在欧拉回路1,3,2,4,5,2,1
5.分析总结:
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;
A.top=1;
A.node[1]=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)//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];
//input
cout<<"\n\t输入顶点数和边数:
";
cin>>n>>m; //n顶点数m边数
memset(M,0,sizeof(M));
for(i=1;i<=n;i++)
degree[i]=0;
for(i=0;i { cout<<"\n\t\t输入第"< "; cin>>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=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(flag[i]==0) { s=1; break; } } if(s==0)//判断有无奇度点 { for(i=1;i<=n;i++) { num=0; for(j=1;j<=n;j++) num+=M[i][j]; if(num%2==1) { s++; break; } } } if(s==0){ T.top=0; Fleury (1); cout<<"\n\t该图的一条欧拉回路: "; for(i=1;i<=m+1;i++){ cout< } } else cout<<"\n\t该图不存在欧拉回路! \n"; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 求欧拉 回路 Fleury 算法