荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 欧拉回路
发信站: 荔园晨风BBS站 (Sat Sep 4 18:14:30 2004), 站内信件
Eulerian Tour
欧拉路径
译 by 孖哥 and tim green
Sample Problem: Riding The Fences
农民John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损
的地方。
John是一个与其他农民一样懒的人。他讨厌骑马，因此从来不两次经过一个一
个栅栏。你必须编一个程序，读入栅栏网络的描述，并计算出一条修栅栏的路径，使
每个栅栏都恰好被经过一次。John能从任何一个顶点(即两个栅栏的交点)开始骑马，
在任意一个顶点结束。
每一个栅栏连接两个顶点，顶点用1到500标号(虽然有的农场并没有500个顶点
)。一个顶点上可连接任意多(>=1)个栅栏。所有栅栏都是连通的(也就是你可以从任
意一个栅栏到达另外的所有栅栏)。
你的程序必须输出骑马的路径(用路上依次经过的顶点号码表示)。我们如果把
输出的路径看成是一个500进制的数，那么当存在多组解的情况下，输出500进制表示
法中最小的一个 (也就是输出第一个数较小的，如果还有多组解，输出第二个数较小
的，等等)。
输入数据保证至少有一个解。
The Abstraction
已知:一幅无向图
寻找一条只过每边一次的路径.这条路径叫欧拉路径(Eulerian tour).如果此路
径和起点和终点是同一点,则此种路径叫欧拉回路.
The Algorithm
判断一幅图有没有欧拉路径或欧拉回路是很简单,有两个不同的规则可用.
* 当且仅当一幅图是相连的(只要你去掉所有度数为0的点)且每个点的度都是
偶数,这幅图有欧拉回路.
* 当且仅当一幅图是相连的且除两点外所有的点的度都是偶数.
* 在第二种情况中,那两个度为奇数的节点一个为起点,剩下的一个是终点.
一个解决此类问题基本的想法是从某个节点开始,然后查出一个从这个点出发回到
这个点的环路径。现在,环已经建立,这种方法保证每个点都被遍历.如果有某个点的
边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直
至所有的边都被遍历。这样，整个图就被连接到一起了。
更正式的说，要找出欧拉路径，就要循环地找出出发点。按以下步骤：
* 任取一个起点,开始下面的步骤
o 如果该点没有相连的点，就将该点加进路径中然后返回。
o 如果该点有相连的点，就列一张相连点的表然后遍历它们直到该点没
有相连的点。(遍历一个点，删除一个点）
o 处理当前的点,删除和这个点相连的边, 在它相邻的点上重复上面的
步骤,把当前这个点加入路径中.
下面是伪代码:
# circuit is a global array
find_euler_circuit
circuitpos = 0
find_circuit(node 1)
# nextnode and visited is a local array
# the path will be found in reverse order
find_circuit(node i)
if node i has no neighbors then
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
else
while (node i has neighbors)
pick a random neighbor node j of node i
delete_edges (node j, node i)
find_circuit (node j)
circuit(circuitpos) = node i
circuitpos = circuitpos + 1
要找欧拉路径, 只要简单的找出一个度为奇数的节点,然后调用 find_circuit 就
可以了.
这两个算法的效率都是 O(m + n), m 是边数， n 是节点数, i如果你用邻接表来
储存图, 有可能会使程序堆栈溢出, 所以你要用自己的堆栈.
Extensions
两个点之间有多条边的图,也可以使用相同的算法。
有自环的图也可以使用这样的算法, 前提是我们自环给这个节点增加的度为2.
如果一个有向图是强连通的 (不考虑入 度出度都是0的点) 并且每个点的入度等
于出度。那么这个图有欧拉回路而这个算法仍然适用,但是你要记得输出时应该从最
后一个开始。
在有向图中寻找一个欧拉路径是十分困难的。
Example problems
Airplane Hopping
忙碌的飞机
给出地图上的城市, 在一些城市之间有航线, 请确定是否存在一条路线,使得飞机
飞遍每一条航线又回到它出发的城市。
分析: 这等价于在一个有向图中找欧拉回路。
Cows on Parade
奶牛游行
农民John有两种牛: 黑色的 Angus和白色的 Jerseys. While marching John的妻
子Joanne送19只母牛去集市时，她注意到4只母牛排要一起的全部的16种情况(e.g.,
bbbb, bbbw, bbwb, bbww, ..., wwww)。当然，一些情况和另一些是有重叠的.
给出 N (2 <= N <= 15), 找出长度最短的一个母牛序列使得N只母牛排在一起的所
有情况在这个序列中都出现过。
分析: 这个图中的顶点是N－1只母牛排在一起的所有情况. [Being at a node co
rresponds to the last N-1 cows matching the node in color.] 当 N = 4,如果
最后3只母牛是 wbw, 那么你就停在节点 wbw 。 因为可能相应的增加w或b到序列的
最后，所以每个点的出度为2。 同样，可能相应的增加w或b到序列的开始,所以每个
点的入度为也2。
这个图是强连通的,并且入度等于出度, 所以存在欧拉回路.。
欧拉回路对应的序列是欧拉回路中第一个点对应的N-1序列加上后面边的颜色。
--
灬 灬 灬灬 灬灬 灬 灬 ════════════════════╗╮
╭╯ 灬 灬▂╱ ＿灬灬ジ ヾ 灬╰╗
║ 灬◢◢ "▔ 灬╱ 灵台无计逃神矢 风雨如磐暗故园 ▁ 灬|"|║
║ ◤, |,╱_ ◣◣ 寄意寒星荃不察 我以我血荐轩辕▕心▏ ◣|║
║ _,|\▄/ \▌◥ ▔ヾ◥◥|║
╚═ "\▌| ▔ | | /" ════════════════════════╯
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.111.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店