欧拉图算法
① 求算法：欧拉路
欧拉回路 【定义】
图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。
具有欧拉回路的图称为欧拉图（简称E图）。
【相关结论】
定理：
一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数。
一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。
求欧拉回路的一种解法
下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。
int num = 0;//标记输出队列
int match[MAX];//标志节点的度，无向图，不区分入度和出度
void solve(int x)
l{
l if(match[x] == 0)
l
l Record[num++] = x;
l
l else
l {
l for(int k =0;k<=500;k++)
l {
l if(Array[x][k] !=0 )
l {
l Array[x][k]--;
l Array[k][x]--;
l match[x]--;
l match[k]--;
l solve(k);
l }
l
l }
l Record[num++] = x;
l }
l}
注意record中的点的排列是输出的到序，因此，如果要输出欧拉路径，需要将record倒过来输出。
求欧拉回路的思路：
循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。
具体步骤：
1。如果此时与该点无相连的点，那么就加入路径中
2。如果该点有相连的点，那么就列一张表，遍历这些点，直到没有相连的点。
3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。
4。这个其实是个递归过程。
--以上为网络的内容
② 图论中，求欧拉路径的算法有哪些
首先要根据欧拉路径的存在条件来判断一个图是否存在欧拉路径,判断条件为如下3条
对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；
如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；
如果超过2个点的度为奇数，那么它就不存在欧拉路了。
然后可以用Fleury算法求欧拉路径,可以参照
http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html
③ 求大神回答，用C语言实现离散数学中的Fleury算法，最后结果要求1、判断是否为欧拉图；2、输出欧拉回路
#include "SqStack.h" //
堆栈的常见操作
#include "Queue.h"//
队列的常见操作
typedef int Graph[200][200];
int v,e;
void DFS(Graph &G
,SqStack &S,int x,int t)
{
int k=0,i,m,a;
Push(S,x);
for(i=t;i<v;i++)
if(G[i][x]>0)
{
k=1;
G[i][x]=0; //
删除此边
G[x][i]=0;
DFS(G
,S,i,0);
break;
}//if,for
if(k==0)
{
Pop(S);
GetTop(S,m);
G[x][m]=1;
G[m][x]=1;
a=x+1;
if(StackLength(S)!=e)
{
Pop(S);
DFS(G
,S,m,a);
}//if
else
Push(S,x);
}//if
}//DFS
int BFSTest(Graph G)
{
int a[200],x,i,k=0;
LinkQueue Q;
InitQueue(Q);
EnQueue(Q,0);
for(i=0;i<v;i++)
a[i]=0;
a[0]=1;
while(!QueueEmpty(Q))
{
DeQueue(Q,x);
for(i=0;i<v;i++)
if(G[x][i]>0)
if(a[i]!=1)
{
a[i]=1;
EnQueue(Q,i);
}//if
}//while
for(i=0;i<v;i++)
if(a[i]==0)
{
k=1;
break;
}
if(k==1)
return 0;
else
return 1;
}
void Euler(Graph &G
,int x)
{
int m;
SqStack S;
InitStack(S);
DFS(G
,S,x,0);
printf("
该图的一个欧拉回路为：
");
while(!StackEmpty(S))
{
GetTop(S,m);
printf("->v%d",m);
Pop(S);
}//while
}
void InputM1(Graph &G)
{
int h,z;
printf("Please input
顶点数和边数
\n");
scanf("%d",&v);
scanf("%d",&e);
for(int i=0;i<v;i++)
for(int j=0;j<v;j++)
G[i][j]=0;
printf("please int the
邻接矩阵的值
(
起点
(
数字
)
终点
(
数字
))
：
\n");
for(int i=0;i<e;i++)
{
scanf("%d",&h);
scanf("%d",&z);
G[h-1][z-1]=1;
G[z-1][h-1]=1;
}//for
}//InputM1
int main()
{
int i,j,sum,k=0;
Graph G;
InputM1(G);
if(BFSTest(G)==0)
{
printf("
该图不是连通图
!\n");
exit(0);
}//if
for(i=0;i<v;i++)
{
sum=0;
for(j=0;j<v;j++)
sum+=G[i][j];
if(sum%2==1)
{
k=1;
break;
}//if
}//for
if(k==1) printf("
该图不存在欧拉回路！
\n");
else
Euler(G,0);
return 1;
}