每周学点大数据 | No.29欧拉回路技术

No.29期

欧拉回路技术

小可：我还有一个问题：今天我们不是要讨论关于磁盘的图算法吗？可是花了好大的劲一直在讨论链表啊？

Mr. 王：其实可以想想，链表本质上也是图，只不过这种图非常特殊，是线性的。不仅如此，这种表的ranking 其实是有很大的实际应用意义的，很多复杂的图算法都是以链表ranking 作为基础或者子操作的。比如，如果我们能够尝试将一棵树T 用链表L 来表示的话，那么对T 的很多操作都可以用对L 的ranking 操作来实现。

小可惊讶地说：真的吗？那树如何用表来表示呢？

Mr. 王：别急，首先我们要了解一种方法，叫作欧拉回路技术。

小可：是一笔画吗？在图中“一笔画”的轨迹就是一个欧拉回路。

Mr. 王：其实很多树由于没有圈的存在都是不能一笔画的，就比如一棵“Y 字形”的树，就不能一笔画，也就不存在欧拉回路了。但是我们在树的范畴中要重新定义一种欧拉回路，称之为“树的欧拉回路”。

树的欧拉回路定义为：从树中的某一点出发，经过任意一条边两次，最终回到出发点的这样一个回路。

小可：哦，如果是这样定义的话，那么每棵树都存在“树的欧拉回路”了。

Mr. 王：比如对于这样的一课树，红色线条就是它的一个欧拉回路，从r 点出发，经过它的每一条边两次，访问整个图，回到r 点。

在内存中，实现树的欧拉回路求解是非常容易的，只要沿着点一个个地搜索下去，就可以很容易地得出结果。不过，如果树中的节点是无明确规律、随机地存放在磁盘中的，那么就不那么容易了。

这时候，如果我们希望用比较高效的方法来解决这个问题的话，就要考虑能否只根据本地的信息。也就是说，对于每个节点，我们只研究它自己和与它相邻的那些边和节点，而不必去考虑树上与之距离较远的其他部分，来求出欧拉回路。

事实上，这是可以实现的，而且实现效率也很高。

小可：如果是这样的话，计算的压力确实可以小很多，那这种思想具体是怎么实现的呢？

Mr. 王：首先，我们要对这棵无向的树做一个小小的变化，将每一条无向边变成两条有向而且方向相反的边的组合。

比如(v,w) 这样一条无向边，我们将其记为(v,w) 和(w,v) 两条单向边的一个组合。这是因为在树的欧拉回路中，每一条边都要走两次，并且一定是方向相反的。

然后，还要进行一个转化，就是将一条边看作是一个链表中的数据节点。也就是说，与这棵树T 等效的链表L 中的每一个数据节点，都是我们前面定义的一条有向边。

小可：那这些边在链表中的连接关系又是怎样的呢？

Mr. 王：嗯，我们来看这个图，假设v 顶点有多条与之相连的边，分别为{v,w1},{v,w2},…,{v,wr}，我们就将链表L 中{wi,v} 的后继表示为{v,wi+1}。

也就是说，{w1,v} 的后继是{v,w2}，{w2,v}的后继就是{v,w3}……这样就能保证对于任意一个节点v，与之相连接的节点w 都能有一去一回的路径。

小可：这样的算法的确能够实现求解一棵树的欧拉回路，同时还能将一棵树T 完全表示成一个链表L。但是这样的算法求解出来的链表L 能够体现树T 的性质吗？比如我想知道，在原来的那棵树T 上，两个节点谁是父节点，谁是子节点呢？

Mr. 王：这样的问题叫作父子关系判定。父子关系判定，就是求在有根树上，两个有一条边相连的节点，谁是父节点，谁是子节点。这在内存中是非常容易判定的，只要从根节点出发进行一次先序遍历，就可以很轻松地解决。

但是在外存中则不然，因为在磁盘中相邻的点是不一定被放在一起的，查找节点的难度会变大，两个在磁盘中不连续存放的节点就需要一次磁盘I/O，就需要考虑I/O 复杂度的问题。

具体的解决办法就是，可以利用我们前面提到的欧拉回路技术。首先，我们以树的根节点为起点，根据树的欧拉回路创建与之等效的链表L。然后，根据下面的条件进行判断：

v = p(w)，当且仅当rank((v,w)) < rank((w,v))

小可：这就是说，如果(v,w) 这条边的rank 小于(w,v) 这条边的rank，那么v 一定是w的父节点。这是为什么呢？

Mr. 王：因为我们是从根节点出发的，如果v 是w的父亲，那么一定会先访问到v，再访问到w，所以先走的就是(v,w) 这条边，等到回来时再走(w,v)，故rank((v,w)) < rank((w,v))。

小可：嗯，如果已经知道了一棵树上节点间的父子关系，那么就更有利于掌握树的结构了。

内容来源：灯塔大数据