有向图的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 阅读(5820)
评论(0) 编辑 收藏 引用 所属分类:
算法基础