有向圖的euler回路定義：從一點出發，經過所有邊僅一次（點可以經過多次），最后回到出發點的閉跡。
算法導論22-3里需要證明有向強連通圖G有euler回路，當且僅當每個節點的入度等于出度。
證明：=> 若有向強連通圖G有euler回路，則可知對于出發點s，假設有x次從s出，那么要想最后回到s，則必須得恰好回到s點x次，因此對于出發點s，入度出度必然相等；假設對于某個非出發點v，若它的出度與入度不相等：假設出度y大于入度x，則第x次從v離開之后就再也不能回到v，則剩余的y-x條出邊不能被訪問到；假設出度y小于入度x，則第y+1次進入v后無法出去；由此可知，對與非出發點v，其入度與出度同樣相等。因此圖G有euler回路，每個節點v的入度等于出度成立。
<= 假設有向強連通圖G的每個節點的入度等于出度，則從出發點s開始遍歷（每條邊只能經過一次，但點可以經過多次），最終必然會回到出發點s（不一定每個節點都走過），這是因為，如果最終沒有回到出發點，則會有一條s->v1->v2->...->vi的路徑，其中vi不等于s，這就可知遍歷過程中進入vi的次數比從vi走出的次數多一次，這樣就肯定至少有一條從vi出的邊沒有被訪問到，所以不成立，因此可知從出發點s開始遍歷，最終必然會回到出發點s。這樣遍歷一次之后會形成一個子回路，這樣在該子回路上的某異與s點的點s1開始繼續遍歷，會形成一個以s1為起始點（也即終止點）的子回路，這兩個回路沒有公共邊，而這兩個子回路明顯可以合并為一個回路，該回路為s->...->e->s1->f->...->s1->...->s，這樣不斷擴展下去必然可以形成一個euler回路，證畢。
求有向強連通euler回路的算法也比較簡單，核心思想還是算法導論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 }
比較費解的就是euler()遞歸函數里打印語句為什么要在循環后而不是循環前，這里還是拿2230的sample input來舉例比較好：
2230形成如下圖示：
當按照上面的代碼如果打印語句在循環之前則會打印：1 2 1 4 1這會形成從1->2->1->4->1的一個子回路，但是接下來由于1點沒有路可走程序會回溯到4點，而4點接著去遍歷2點，然后就會打印2，這就會形成1 2 1 4 1 2，而這顯然遍歷錯誤！！！
正確的應該是在遍歷子回路完畢之后再打印起始節點1，然后回溯到最后進入1時的節點4，然后從4在去遍歷形成新的子回路（4->2->3->2->4->3->4），然后再打印4，然后再回溯到新的子回路中最后一個進入4的節點3，然后再從3擴展子回路（實際上3已經沒有子回路了），然后打印3，然后3再退回到4，然后4再擴展新的子回路（已經沒有了）然后打印4，然后4再回退到2，依次類推，這樣就會形成一個按找遍歷順序逆序的嵌套回路打?。。。?！大家明白了吧？對于這道題，按照遍歷順序逆序打印沒有問題，因為這道題的邊都是雙向的，但是對于一般的求euler回路的問題就不能直接在循環后打印了，需要使用一個棧保存結果，然后在遍歷完后輸出棧里的內容！
posted on 2012-08-22 00:15
myjfm 閱讀(5926)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎