發現
歐拉回路是數學家歐拉在研究著名的德國哥尼斯堡(Koenigsberg)七橋問題時發現的。如圖1所示，流經哥尼斯堡的普雷格爾河中有兩個島，兩個島與兩岸共4處陸地通過7座楊彼此相聯。7橋問題就是如何能從任一處陸地出發，經過且經過每個橋一次後回到原出發點。
這個問題可抽象為一個如圖2所示的數學意義上的圖，其中4個結點分别表示與4塊陸土Il對應，如結點C對應河岸C，結點A對應島A等，而結點之間的邊表示7座橋。
歐拉由此提出了著名的歐拉定理。
1）歐拉路：通過圖中所有邊的簡單路。
2）歐拉回路：閉合的歐拉路。
3）歐拉圖：包含歐拉回路的圖。
判斷
以下判斷基于此圖的基圖連通。
無向圖存在歐拉回路的充要條件
一個無向圖存在歐拉回路，當且僅當該圖所有頂點度數都為偶數，且該圖是連通圖。
有向圖存在歐拉回路的充要條件
一個有向圖存在歐拉回路，所有頂點的入度等于出度且該圖是連通圖。
混合圖存在歐拉回路條件
要判斷一個混合圖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
解法
無向圖歐拉回路解法
求歐拉回路的一種解法
下面是無向圖的歐拉回路輸出代碼：注意輸出的前提是已經判斷圖确實是歐拉回路。
C語言代碼，不全，請不要直接粘貼。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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代碼:
求無向圖的歐拉回路（遞歸實現）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
program euler;
const maxn=10000;{頂點數上限}
maxm=100000;{邊數上限}
typetnode=^tr;
tr=record
f,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;{原圖中是否存在歐拉回路}
procedurebuild(ta,tb:longint);{在鄰接表中建立邊(ta,tb)}
vart1,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;
proceduremerge(a,b:longint);{在并查集中将a,b兩元素合并}
varoa,ob:longint;
begin
oa:=a;
whilefa[a]<>adoa:=fa[a];
fa[oa]:=a;
ob:=b;
whilefa[b]<>bdob:=fa[b];
fa[ob]:=b;
ifa<>bthenbegin
dec(bl);{合并後，基圖的極大連通子圖個數減少1}
ifrank[a]=rank[b]theninc(rank[a]);
ifrank[a]>rank[b]thenfa[b]:=aelsefa[a]:=b;
end;
end;
procedureinit;{初始化}
vari,ta,tb:longint;
begin
fillchar(fa,sizeof(fa),0);
fillchar(rank,sizeof(rank),0);
fillchar(d,sizeof(d),0);
readln(n,m);
fori:=1tondofa[i]:=i;
bl:=n;
fori:=1tomdobegin
readln(ta,tb);
build(ta,tb);
inc(d[tb]);
inc(d[ta]);
merge(ta,tb);
end;
end;
proceduresearch(i:longint);{以i為出發點尋找歐拉回路}
varte:tnode;
begin
te:=g[i];
whilete<>nildobegin
ifnotte^.althenbegin
te^.al:=true;
te^.rev^.al:=true;
search(te^.t);
list[tot]:=te;
dec(tot);
end;
te:=te^.next;
end;
end;
proceduremain;{主過程}
vari:longint;
begin
o:=false;
fori:=1tondo
ifd[i]=0thendec(bl);{排除孤立點的影響}
ifbl<>1thenexit;{原圖不連通，無解}
fori:=1tondo
ifodd(d[i])thenexit;{存在奇點，無解}
o:=true;
fori:=1tondo
ifd[i]<>0thenbreak;
tot:=m;
search(i);{從一個非孤立點開始尋找歐拉回路}
end;
procedureprint;{輸出結果}
vari:longint;
begin
ifnotothenwriteln('Nosolution.')elsebegin
writeln(list[1]^.f);
fori:=1tomdowriteln(list[i]^.t);
end;
end;
begin
init;
main;
print;
end.
|
注意record中的點的排列是輸出的倒序，因此，如果要輸出歐拉路徑，需要将record倒過來輸出。
求歐拉回路的思路：
循環的找到出發點。從某個節點開始，然後查出一個從這個出發回到這個點的環路徑。這種方法不保證每個邊都被遍曆。
如果有某個點的邊沒有被遍曆就讓這個點為起點，這條邊為起始邊，把它和當前的環銜接上。這樣直至所有的邊都被遍曆。這樣，整個圖就被連接到一起了。
具體步驟：
1。如果此時與該點無相連的點，那麼就加入路徑中
2。如果該點有相連的點，那麼就加入隊列之中，遍曆這些點，直到沒有相連的點。
3。處理當前的點，删除走過的這條邊，并在其相鄰的點上進行同樣的操作，并把删除的點加入到路徑中去。
4。這個其實是個遞歸過程。
相關詞條
相關搜索
其它詞條
