欧拉算法教程（每周学点大数据）

转载声明

本文为灯塔大数据原创内容，欢迎个人转载至朋友圈，其他机构转载请在文章开头标注：

“转自：灯塔大数据；DTbigdata”

编者按：灯塔大数据将每周持续推出《从零开始学大数据算法》的连载，本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作，以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用，带我们在大数据技术的海洋里徜徉~每周五定期更新，欢迎来做客呦！

上期回顾&查看方式：

在上一期中，我们介绍了关于磁盘中图算法的问题，通过详细讲解“独立集”来介绍一种基础的算法——“表排序”。在本期，我们将学习表排序的一种应用——欧拉回路技术，并详细讲解如何在内存中，实现树的欧拉回路。

PS：了解上期详细内容，请在自定义菜单栏中点击“文章精选”—“技术连载”，进行查看。

No.29期 欧拉回路技术

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

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))。

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

下期精彩预告：

经过学习，我们介绍了表排序的一种应用——欧拉回路技术，并详细讲解如何在内存中，实现树的欧拉回路。在下一期中，我们将介绍父子判定的应用——前序计数，运用欧拉回路技术的方法，及将树存储为链表的的策略来详细讲解。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！

内容来源：灯塔大数据

【灯塔大数据】微信公众号介绍：中国电大数据技术创新，自主研发了业内领先的“灯塔”大数据行业应用创新平台，灯塔面向市场研究、广告营销、商业地理、金融征信、人力资源等诸多行业领域，提供零售研究、消费者研究、店铺选址、精准营销、泛义征信，背景调查等服务，助力企业在大数据时代扬帆远航。

微信公众号【灯塔大数据】关键字信息：

【IDC】 下载IDC报告原文

【六个关键词】 下载运营商大数据PPT

【大数据日】 下载演讲材料

【十月融资】下载2016年10月投融资月报

【网络安全】获取国民网络安全报告全文

【23个理由】下载《大数据让你兴奋的23个理由》电子书

【思维导图】下载12种工具的获取方式

【 灯塔 】 查看更多关键字回复