每周学点大数据 | 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))。

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

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-03-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏云霄雨霁

函数依赖总结

11920
来自专栏杨建荣的学习笔记

Python之Numpy初识

今天翻了下计划,要学习Numpy了,所以得调动脑细胞的积极性,看看能有什么收获。 首先得了解下什么是Numpy,从我的印象中,一般提到这个工具都会和机器学习关...

370110
来自专栏wym

牛客练习赛19 E托米的饮料

链接:https://www.nowcoder.com/acm/contest/111/E 来源:牛客网

10410
来自专栏数据结构与算法

P1095 守望者的逃离

题目描述 恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,...

29960
来自专栏简书专栏

Python数据科学库-小测验

答:np.arange、np.array、np.ones、np.zeros、np.full

20510
来自专栏枕边书

空间索引 - 四叉树

前言 作为程序员,应该都对二叉树都不陌生,我们都知道二叉树的变体二叉查找树,非常适合用来进行对一维数列的存储和查找,可以达到 O(logn) 的效率;我们在用二...

473100
来自专栏代码永生,思想不朽

utf8中文字符串的多模式匹配算法的优化

上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

56030
来自专栏Golang语言社区

麻将游戏数据结构和AI算法

用休息时间零零散散写完了网络麻将游戏,感觉其中有不少值得记录的东西。 基础数据结构     数据结构确定决定了程序的开发难易程度,就像是游戏的骨架,对于电脑AI...

1.2K20
来自专栏人工智能

如何使用tableaux进行逻辑计算

原文作者:Miguel Diaz Kusztrich

97480
来自专栏Flutter入门

WAV文件格式解析及处理

RIFF全称为资源互换文件格式(Resources Interchange File Format),是Windows下大部分多媒体文件遵循的一种文件结构。RI...

1.9K20

扫码关注云+社区

领取腾讯云代金券