求歐拉迴路演算法

A. 歐拉迴路matlab演算法實現

詳細描述一下演算法。回答你的問題時，只答程序有關的，演算法是你的，需要你提供

B. 求大神回答，用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;
}

C. 歐拉迴路的解法

無向圖歐拉迴路解法
求歐拉迴路的一種解法
下面是無向圖的歐拉迴路輸出代碼：注意輸出的前提是已經判斷圖確實是歐拉迴路。
C語言代碼，不全，請不要直接粘貼。 intnum=0;//標記輸出隊列intmatch[MAX];//標志節點的度，無向圖，不區分入度和出度voidsolve(intx){if(match[x]==0)Record[num++]=x;else{for(intk=0;k<=500;k++){if(Array[x][k]!=0){Array[x][k]--;Array[k][x]--;match[x]--;match[k]--;solve(k);}}Record[num++]=x;}}pascal代碼:
求無向圖的歐拉迴路（遞歸實現） programeuler;constmaxn=10000;{頂點數上限}maxm=100000;{邊數上限}typetnode=^tr;tr=recordf,t:longint;{邊的起始點和終止點}al:boolean;{訪問標記}rev,next:tnode;{反向邊和鄰接表中的下一條邊}end;varn,m,bl:longint;{頂點數，邊數，基圖的極大連通子圖個數}tot:longint;g:array[1..maxn]oftnode;d:array[1..maxn]oflongint;{頂點的度}fa,rank:array[1..maxn]oflongint;{並查集中元素父結點和啟發函數值}list:array[1..maxm]oftnode;{最終找到的歐拉迴路}o:boolean;{原圖中是否存在歐拉迴路}procerebuild(ta,tb:longint);{在鄰接表中建立邊(ta,tb)}vart1,t2:tnode;begint1:=new(tnode);t2:=new(tnode);t1^.f:=ta;t1^.t:=tb;t1^.al:=false;t1^.rev:=t2;t1^.next:=g[ta];g[ta]:=t1;t2^.f:=tb;t2^.t:=ta;t2^.al:=false;t2^.rev:=t1;t2^.next:=g[tb];g[tb]:=t2;end;proceremerge(a,b:longint);{在並查集中將a,b兩元素合並}varoa,ob:longint;beginoa:=a;whilefa[a]<>adoa:=fa[a];fa[oa]:=a;ob:=b;whilefa[b]<>bdob:=fa[b];fa[ob]:=b;ifa<>bthenbegindec(bl);{合並後，基圖的極大連通子圖個數減少1}ifrank[a]=rank[b]theninc(rank[a]);ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;end;end;procereinit;{初始化}vari,ta,tb:longint;beginfillchar(fa,sizeof(fa),0);fillchar(rank,sizeof(rank),0);fillchar(d,sizeof(d),0);readln(n,m);fori:=1tondofa[i]:=i;bl:=n;fori:=1tomdobeginreadln(ta,tb);build(ta,tb);inc(d[tb]);inc(d[ta]);merge(ta,tb);end;end;proceresearch(i:longint);{以i為出發點尋找歐拉迴路}varte:tnode;beginte:=g[i];whilete<>nildobeginifnotte^.althenbeginte^.al:=true;te^.rev^.al:=true;search(te^.t);list[tot]:=te;dec(tot);end;te:=te^.next;end;end;proceremain;{主過程}vari:longint;begino:=false;fori:=1tondoifd[i]=0thendec(bl);{排除孤立點的影響}ifbl<>1thenexit;{原圖不連通，無解}fori:=1tondoifodd(d[i])thenexit;{存在奇點，無解}o:=true;fori:=1tondoifd[i]<>0thenbreak;tot:=m;search(i);{從一個非孤立點開始尋找歐拉迴路}end;procereprint;{輸出結果}vari:longint;beginifnotothenwriteln('Nosolution.')elsebeginwriteln(list[1]^.f);fori:=1tomdowriteln(list[i]^.t);end;end;begininit;main;print;end.注意record中的點的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要將record倒過來輸出。
求歐拉迴路的思路：
循環的找到出發點。從某個節點開始，然後查出一個從這個出發回到這個點的環路徑。這種方法不保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點，這條邊為起始邊，把它和當前的環銜接上。這樣直至所有的邊都被遍歷。這樣，整個圖就被連接到一起了。
具體步驟：
1。如果此時與該點無相連的點，那麼就加入路徑中
2。如果該點有相連的點，那麼就加入隊列之中，遍歷這些點，直到沒有相連的點。
3。處理當前的點，刪除走過的這條邊，並在其相鄰的點上進行同樣的操作，並把刪除的點加入到路徑中去。
4。這個其實是個遞歸過程。

D. 圖論中，求歐拉路徑的演算法有哪些

首先要根據歐拉路徑的存在條件來判斷一個圖是否存在歐拉路徑,判斷條件為如下3條
對於一個無向圖，如果它每個點的度都是偶數，那麼它存在一條歐拉迴路；
如果有且僅有2個點的度為奇數，那麼它存在一條歐拉路；
如果超過2個點的度為奇數，那麼它就不存在歐拉路了。
然後可以用Fleury演算法求歐拉路徑,可以參照
http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html

E. 急求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

F. 概要描述一個演算法，判斷一個用鄰接矩陣表示的連通圖是否具有歐拉迴路。該演算法效率類型如何

演算法如下：
設鄰接矩陣維度為n*n，將鄰接矩陣進行標准化轉為概率轉移矩陣，方法是每一行元素除以行和保證每行和為1（由於連通，每行和一定大於零，所以除法可實現）
首先判斷矩陣對角線上是否有>0的元素，如有證明有歐拉迴路（自環），否則進行下一步
第二步將矩陣平方，判斷矩陣對角線上是否有>0的元素，如有證明有歐拉迴路（兩個節點的環），否則進行下一步
以此類推，直到計算矩陣的n次方，判斷對角線上是否有>0的元素，如有證明有歐拉迴路，此時仍沒有>0的元素證明該連通圖沒有歐拉迴路

這個方法的依據是，如果將鄰接矩陣標准化為概率轉移矩陣，那麼對矩陣進行k次方，得到的矩陣第(i,j)個元素的意義就是通過k步使得從i走到j的概率，那麼對角線(i,i)代表的就是從i經k步回到i的概率，這個概率大於零就代表有一條迴路。對於一個共有n個節點的有歐拉迴路的連通圖，最短的歐拉迴路結點個數一定小於等於n，所以如果n次方後還沒有出現迴路概率就可以判斷沒有迴路了

演算法效率類型我不太清楚是怎麼算的……不過這個演算法方面，標准化矩陣的部分運算復雜度不超過n，之後至多進行n步，每一步的矩陣冪大概可以到O(n)復雜度，判斷至多也就是O(n)，所以這個復雜度不超過O(n^2)的吧

G. 圖論中的"歐拉迴路"有什麼應用，似乎不如"漢密爾頓迴路"實用啊

就是一筆畫問題啊，確實不是實用的，只是很數學的一個問題。

H. fleury演算法尋找歐拉迴路

#include <iostream>
using namespace std;

int** init(int* count) {
int v_count;
char* str = new char();
int ** Euler;

cout<<"Input the Vertexs' count: "<<endl;
cin>>v_count;
*count = v_count;
Euler = (int **) malloc (sizeof(int *) * v_count);
for (int i = 0; i < v_count; i++) {
Euler[i] = (int *) malloc (sizeof(int) * v_count);
memset(Euler[i], 0, sizeof(int) * v_count);
}
do {
int v_1, v_2;
cout<<"Input a Edge (ex. 2,3 or \'exit\' to exit): "<<endl;
cin>>str;
if (strcmp(str, "exit") == 0) {
break;
}
sscanf(str, "%d,%d", &v_1, &v_2);
if (v_1 < 0 || v_1 >= v_count || v_2 < 0 || v_2 >= v_count) {
fprintf(stderr, "Error : must be in (%d~%d)\n", 0, v_count - 1);
continue;
}
Euler[v_1][v_2] = Euler[v_2][v_1] = 1;
} while(true);

return Euler;
}

bool isEulerCircle(int** Euler, int count) {
int i, j, degree;

for(i = 0; i < count; i++) {
degree = 0;
for(j = 0; j < count; j++) {
degree+=Euler[i][j];
}
if(degree % 2 == 1)
return false;
}
return true;
}

void Fleury(int** Euler, int count) {
int i, j, v, flg = 1, large = 0;

for(i = 0; i < count; i++) {
int tmp = 0;
for(j = 0; j < count; j++) {
tmp += Euler[i][j];
}
if (tmp > large)
v = i;
}
while(flg) {
flg = 0;
for(i = 0; i < count; i++) {
if(Euler[v][i] == 1) {
Euler[v][i] = 0;
Euler[i][v] = 0;
flg = 1;
printf("From %d to %d\n", v, i);
v = i;
}
}
}
}

void main(){
int ** Euler;
int count;

Euler = init(&count);
if(!isEulerCircle(Euler, count)) {
printf("The Euler Circle is wrong!\n");
exit(0);
}
Fleury(Euler, count);
}

I. 歐拉迴路中，頂點度數到底是什麼

圖G的一個迴路，若它恰通過G中每條邊一次,則稱該迴路為歐拉(Euler)迴路。
具有歐拉迴路的圖稱為歐拉圖（簡稱E圖）。
無向圖存在歐拉迴路的充要條件
一個無向圖存在歐拉迴路，當且僅當該圖所有頂點度數都是偶數且該圖是連通圖。
有向圖存在歐拉迴路的充要條件
一個有向圖存在歐拉迴路，所有頂點的入度等於出度且該圖是連通圖，或者 一個頂點的度數為1，另一個度數為-1，其他頂點的度數為0。
混合圖存在歐拉迴路條件
要判斷一個混合圖G（V,E）（既有有向邊又有無向邊）是歐拉圖，方法如下：
假設有一張圖有向圖G'，在不論方向的情況下它與G同構。並且G'包含了G的所有有向邊。那麼如果存在一個圖G'使得G'存在歐拉迴路，那麼G就存在歐拉迴路。
其思路就將混合圖轉換成有向圖判斷。實現的時候，我們使用網路流的模型。現任意構造一個G'。用Ii表示第i個點的入度，Oi表示第i個點的出度。如果存在一個點k，|Ok-Ik|mod 2=1，那麼G不存在歐拉迴路。接下來則對於所有Ii>Oi的點從源點連到i一條容量為(Ii-Oi)/2的邊，對於所有Ii<Oi的點從i連到匯點一條容量為(Oi-Ii)/2的邊。如果對於節點U和V，無向邊（U，V）∈E，那麼U和V之間互相建立容量為無限大的邊。如果此網路的最大流等於∑|Ii-Oi|/2，那麼就存在歐拉迴路。
編輯本段解法
無向圖歐拉迴路解法
求歐拉迴路的一種解法
下面是無向圖的歐拉迴路輸出代碼：注意輸出的前提是已經判斷圖確實是歐拉迴路。
C語言代碼，不全，請不要直接粘貼。
int num = 0;//標記輸出隊列
int match[MAX];//標志節點的度，無向圖，不區分入度和出度
void solve(int x)
{
if(match[x] == 0)
Record[num++] = x;
else
{
for(int k =0;k<=500;k++)
{
if(Array[x][k] !=0 )
{
Array[x][k]--;
Array[k][x]--;
match[x]--;
match[k]--;
solve(k);
}
}
Record[num++] = x;
}
}
pascal代碼:
求無向圖的歐拉迴路（遞歸實現）
program euler;
const maxn=10000;{頂點數上限}
maxm=100000;{邊數上限}
type tnode=^tr;
tr=record
f,t:longint;{邊的起始點和終止點}
al:boolean;{訪問標記}
rev,next:tnode;{反向邊和鄰接表中的下一條邊}
end;
var n,m,bl:longint;{頂點數，邊數，基圖的極大連通子圖個數}
tot:longint;
g:array[1..maxn] of tnode;
d:array[1..maxn] of longint;{頂點的度}
fa,rank:array[1..maxn] of longint;{並查集中元素父結點和啟發函數值}
list:array[1..maxm] of tnode;{最終找到的歐拉迴路}
o:boolean;{原圖中是否存在歐拉迴路}
procere build(ta,tb:longint);{在鄰接表中建立邊(ta, tb)}
var t1,t2:tnode;
begin
t1:=new(tnode);
t2:=new(tnode);
t1^.f:=ta;
t1^.t:=tb;
t1^.al:=false;
t1^.rev:=t2;
t1^.next:=g[ta];
g[ta]:=t1;
t2^.f:=tb;
t2^.t:=ta;
t2^.al:=false;
t2^.rev:=t1;
t2^.next:=g[tb];
g[tb]:=t2;
end;
procere merge(a,b:longint);{在並查集中將a, b兩元素合並}
var oa,ob:longint;
begin
oa:=a;
while fa[a]<>a do a:=fa[a];
fa[oa]:=a;
ob:=b;
while fa[b]<>b do b:=fa[b];
fa[ob]:=b;
if a<>b then begin
dec(bl);{合並後，基圖的極大連通子圖個數減少1}
if rank[a]=rank[b] then inc(rank[a]);
if rank[a]>rank[b] then fa[b]:=a else fa[a]:=b;
end;
end;
procere init;{初始化}
var i,ta,tb:longint;
begin
fillchar(fa,sizeof(fa),0);
fillchar(rank,sizeof(rank),0);
fillchar(d,sizeof(d),0);
readln(n,m);
for i:=1 to n do fa[i]:=i;
bl:=n;
for i:=1 to m do begin
readln(ta,tb);
build(ta,tb);
inc(d[tb]);
inc(d[ta]);
merge(ta,tb);
end;
end;
procere search(i:longint);{以i為出發點尋找歐拉迴路}
var te:tnode;
begin
te:=g[i];
while te<>nil do begin
if not te^.al then begin
te^.al:=true;
te^.rev^.al:=true;
search(te^.t);
list[tot]:=te;
dec(tot);
end;
te:=te^.next;
end;
end;
procere main;{主過程}
var i:longint;
begin
o:=false;
for i:=1 to n do
if d[i]=0 then dec(bl);{排除孤立點的影響}
if bl<>1 then exit;{原圖不連通，無解}
for i:=1 to n do
if odd(d[i]) then exit;{存在奇點，無解}
o:=true;
for i:=1 to n do
if d[i]<>0 then break;
tot:=m;
search(i);{從一個非孤立點開始尋找歐拉迴路}
end;
procere print;{輸出結果}
var i:longint;
begin
if not o then writeln('No solution.') else begin
writeln(list[1]^.f);
for i:=1 to m do writeln(list[i]^.t);
end;
end;
begin
init;
main;
print;
end.
注意record中的點的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要將record倒過來輸出。
求歐拉迴路的思路：
循環的找到出發點。從某個節點開始，然後查出一個從這個出發回到這個點的環路徑。這種方法不保證每個邊都被遍歷。如果有某個點的邊沒有被遍歷就讓這個點為起點，這條邊為起始邊，把它和當前的環銜接上。這樣直至所有的邊都被遍歷。這樣，整個圖就被連接到一起了。
具體步驟：
1。如果此時與該點無相連的點，那麼就加入路徑中
2。如果該點有相連的點，那麼就加入隊列之中，遍歷這些點，直到沒有相連的點。
3。處理當前的點，刪除走過的這條邊，並在其相鄰的點上進行同樣的操作，並把刪除的點加入到路徑中去。
4。這個其實是個遞歸過程。