有向圖的euler回路定義：從一點(diǎn)出發(fā)，經(jīng)過所有邊僅一次（點(diǎn)可以經(jīng)過多次），最后回到出發(fā)點(diǎn)的閉跡。
算法導(dǎo)論22-3里需要證明有向強(qiáng)連通圖G有euler回路，當(dāng)且僅當(dāng)每個(gè)節(jié)點(diǎn)的入度等于出度。
證明：=> 若有向強(qiáng)連通圖G有euler回路，則可知對(duì)于出發(fā)點(diǎn)s，假設(shè)有x次從s出，那么要想最后回到s，則必須得恰好回到s點(diǎn)x次，因此對(duì)于出發(fā)點(diǎn)s，入度出度必然相等；假設(shè)對(duì)于某個(gè)非出發(fā)點(diǎn)v，若它的出度與入度不相等：假設(shè)出度y大于入度x，則第x次從v離開之后就再也不能回到v，則剩余的y-x條出邊不能被訪問到；假設(shè)出度y小于入度x，則第y+1次進(jìn)入v后無法出去；由此可知，對(duì)與非出發(fā)點(diǎn)v，其入度與出度同樣相等。因此圖G有euler回路，每個(gè)節(jié)點(diǎn)v的入度等于出度成立。
<= 假設(shè)有向強(qiáng)連通圖G的每個(gè)節(jié)點(diǎn)的入度等于出度，則從出發(fā)點(diǎn)s開始遍歷（每條邊只能經(jīng)過一次，但點(diǎn)可以經(jīng)過多次），最終必然會(huì)回到出發(fā)點(diǎn)s（不一定每個(gè)節(jié)點(diǎn)都走過），這是因?yàn)椋绻罱K沒有回到出發(fā)點(diǎn)，則會(huì)有一條s->v1->v2->...->vi的路徑，其中vi不等于s，這就可知遍歷過程中進(jìn)入vi的次數(shù)比從vi走出的次數(shù)多一次，這樣就肯定至少有一條從vi出的邊沒有被訪問到，所以不成立，因此可知從出發(fā)點(diǎn)s開始遍歷，最終必然會(huì)回到出發(fā)點(diǎn)s。這樣遍歷一次之后會(huì)形成一個(gè)子回路，這樣在該子回路上的某異與s點(diǎn)的點(diǎn)s1開始繼續(xù)遍歷，會(huì)形成一個(gè)以s1為起始點(diǎn)（也即終止點(diǎn)）的子回路，這兩個(gè)回路沒有公共邊，而這兩個(gè)子回路明顯可以合并為一個(gè)回路，該回路為s->...->e->s1->f->...->s1->...->s，這樣不斷擴(kuò)展下去必然可以形成一個(gè)euler回路，證畢。
求有向強(qiáng)連通euler回路的算法也比較簡單，核心思想還是算法導(dǎo)論22-3里提示的不共邊子回路合并，借用poj2230題來寫模板吧：
1 #include <cstdio>
2 #include <vector>
3
4 #define MAX_VERTEX 10005
5
6 typedef struct {
7 int end_vertex;
8 int visited;
9 } Edge;
10
11 int Nvertex;
12 int Nedge;
13 std::vector<Edge> vertex[MAX_VERTEX];
14
15 static void input() {
16 int i, u, v;
17 Edge tmp;
18 tmp.visited = 0;
19 scanf("%d%d", &Nvertex, &Nedge);
20 for (i = 0; i < Nedge; ++i) {
21 scanf("%d%d", &u, &v);
22 tmp.end_vertex = u;
23 vertex[v].push_back(tmp);
24 tmp.end_vertex = v;
25 vertex[u].push_back(tmp);
26 }
27 }
28
29 static void euler(int x) {
30 int i;
31 for (i = vertex[x].size() - 1; i >= 0; --i) {
32 if (!vertex[x][i].visited) {
33 vertex[x][i].visited = 1;
34 euler(vertex[x][i].end_vertex);
35 }
36 }
37 printf("%d\n", x);
38 }
39
40 int main() {
41 input();
42 euler(1);
43 return 0;
44 }
比較費(fèi)解的就是euler()遞歸函數(shù)里打印語句為什么要在循環(huán)后而不是循環(huán)前，這里還是拿2230的sample input來舉例比較好：
2230形成如下圖示：
當(dāng)按照上面的代碼如果打印語句在循環(huán)之前則會(huì)打印：1 2 1 4 1這會(huì)形成從1->2->1->4->1的一個(gè)子回路，但是接下來由于1點(diǎn)沒有路可走程序會(huì)回溯到4點(diǎn)，而4點(diǎn)接著去遍歷2點(diǎn)，然后就會(huì)打印2，這就會(huì)形成1 2 1 4 1 2，而這顯然遍歷錯(cuò)誤！！！
正確的應(yīng)該是在遍歷子回路完畢之后再打印起始節(jié)點(diǎn)1，然后回溯到最后進(jìn)入1時(shí)的節(jié)點(diǎn)4，然后從4在去遍歷形成新的子回路（4->2->3->2->4->3->4），然后再打印4，然后再回溯到新的子回路中最后一個(gè)進(jìn)入4的節(jié)點(diǎn)3，然后再從3擴(kuò)展子回路（實(shí)際上3已經(jīng)沒有子回路了），然后打印3，然后3再退回到4，然后4再擴(kuò)展新的子回路（已經(jīng)沒有了）然后打印4，然后4再回退到2，依次類推，這樣就會(huì)形成一個(gè)按找遍歷順序逆序的嵌套回路打印！！！！大家明白了吧？對(duì)于這道題，按照遍歷順序逆序打印沒有問題，因?yàn)檫@道題的邊都是雙向的，但是對(duì)于一般的求euler回路的問題就不能直接在循環(huán)后打印了，需要使用一個(gè)棧保存結(jié)果，然后在遍歷完后輸出棧里的內(nèi)容！
posted on 2012-08-22 00:15
myjfm 閱讀(5924)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)