欧拉路

发表于 | 分类于 | | 阅读次数:

有一条名为Pregel的河流经过Konigsberg城。城中有7座桥，把河中的两个岛与河岸连接起来。当地居民热衷于一个难题：是否存在一条线路，可以不重复的走遍7座桥。这就是著名的七桥问题。它由大数学家欧拉首先提出，并给出完美的解答，所以这样的一条路也叫欧拉道路。
Elur

参考

《算法竞赛入门经典（2）》

Ps：图片来自维基百科

欧拉路（欧拉回路）

将七桥问题用图论的形式表达：能否从无向图中的一个结点出发走出一条道路，每条边恰好经过一次。

可以发现，除起点和终点外其它点的“进”和“出”是对应的，即其它点的度数应为偶数。这也是判断欧拉路是否存在的充分条件–如果一个无向图是连通的，且最多只有两个奇点，则一定存在欧拉道路。如果有两个奇点，则必须从其中一个奇点出发，另一个奇点终止；如果奇点不存在，则可以从任意点出发，最终一点会回到该点（欧拉回路）

类似的对有向图来说–最多只能有两个点的入度不等于出度， 而且必须是其中一个点的出度恰好比入度大1（把它作为起点），另一个的入度比出度大1（把它作为终点）。还有一个前提条件：在忽略边的方向后，图必须是连通的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void elur(int u){
    for(int v = 0; v < n; v++){
        if(G[u][v] && !vis[u][v]){
            vis[u][v] = vis[v][u] = 1;
            elur(v);
        }
        printf("%d %d\n", u, v);
    }
}

//说明
1.上面的代码适用于无向图，但是可以改为有向图：把vis[u][v] = vis[v][u] = 1改成vis[u][v] = 1
2.上面的代码是逆序打印，可以把printf改为push，将边压栈，最后顺序打印。