求欧拉回路的Fleury算法教学提纲.doc

求欧拉回路的Fleury算法

精品资料
一、 实验内容：
判断图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=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。

3. 数据输入：
边数5，点数6
相关联的点1 2
1 3
2 5
4 2
3 2
4 5
4. 运行结果：
存在欧拉回路 1，3，2，4，5，2，1
5. 分析总结：
Fleury算法是求欧拉图的十分有效的算法，在执行过程中需要用到类似于图的深度优先遍历，因为该算法就是需要将已找到的路径不断的扩展下去，直到将所有边扩展进路径。

判断是否为欧拉图
（连通性和奇度点）
图　Ｇ
ｙ
ｎ
输出无欧拉回路
Ｐ0=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算法流程图

三、 完整源程序

仅供学习与交流，如有侵权请联系网站删除 谢谢6
#include <iostream.h>
#include <stdio.h>
#include <string.h>

struct stack
{
int top , node[81];

} T,F,A; //顶点的堆栈

int M[81][81]; //图的邻接矩阵
int n;
int degree[81];

bool brigde(int i,int j)
{
int flag[81],t,s;
for(s=1;s<=n;s++)
flag[s]=0;
if(degree[i]==1)
return false;
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;
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.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);
}
}
}

void main()
{
int m , 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 < m; i ++)
{
cout<<"\n\t\t输入第"<<i+1<<"边的顶点:";
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<<T.node[i]<<" ";
}
}
else
cout<<"\n\t该图不存在欧拉回路!\n";
}