fleury演算法
⑴ 急求c++fleury演算法歐拉迴路代碼
1#include <stdio.h>
2#include <string.h>
3
4
5struct stack
6{int top , node[210];} f; //頂點的堆棧
7
8int a[201][201]; //圖的鄰接矩陣
9
10int n;
11
12void dfs(int x) //圖的深度優先遍歷
13{
14int i;
15
16f.top ++; f.node[f.top] = x;
17
18for (i = 1; i <= n; i ++)
19
20 if (a[i][x] > 0)
21 {
22 a[i][x] = 0; a[x][i] = 0; //刪除此邊
23
24 dfs(i);
25
26 break;
27 }
28}
29
30void Euler(int x) //歐拉路演算法
31{
32int i , b;
33
34f.top = 0; f.node[f.top] = x; //入棧
35
36while (f.top >= 0)
37{
38 b = 0;
39
40 for (i = 1; i <= n; i ++)
41 if (a[f.node[f.top]][i] > 0)
42 {b = 1; break;}
43
44 if (b == 0) //如果沒有點可以擴展，輸出並出棧
45 {
46 printf("%d " , f.node[f.top]);
47
48 f.top --;
49 }
50 else {f.top --; dfs(f.node[f.top+1]);} //如果有，就DFS
51 }
52}
53
54int main()
55{
56
57int m , s , t , num , i , j , start;
58
59 //input
60
61 scanf("%d %d" , &n , &m); //n頂點數 m邊數
62
63 memset(a , 0 , sizeof(a));
64
65 for (i = 0; i < m; i ++)
66 {
67 scanf("%d %d" , &s , &t);
68 a[s][t] = 1; a[t][s] = 1;
69 }
70
71
72 //判斷是否存在歐拉迴路
73
74 s = 0; start = 1;
75
76 for (i = 1; i <= n; i ++)
77 {
78 num = 0;
79
80 for (j = 1; j <= n; j ++)
81 num += a[i][j];
82
83 if (num % 2 == 1)
84{start = i; s ++;}
85 }
86
87 if ((s == 0) || (s == 2))
88Euler(start);
89 else printf("No Euler path\n");
90
91 getchar(); getchar();
92 return 0;
93}
94
⑵ 求大神回答，用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;
}
⑶ 圖論中，求歐拉路徑的演算法有哪些
首先要根據歐拉路徑的存在條件來判斷一個圖是否存在歐拉路徑,判斷條件為如下3條
對於一個無向圖，如果它每個點的度都是偶數，那麼它存在一條歐拉迴路；
如果有且僅有2個點的度為奇數，那麼它存在一條歐拉路；
如果超過2個點的度為奇數，那麼它就不存在歐拉路了。
然後可以用Fleury演算法求歐拉路徑,可以參照
http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html