专栏首页灯塔大数据每周学点大数据 | No.31拓扑排序

每周学点大数据 | No.31拓扑排序

No.31期

拓扑排序

Mr. 王:很好,你还记得这个问题。接下来我们来讨论另一种磁盘中的大数据算法策略,叫作时间前向处理方法。在这种策略中,我会讲解求解最大独立集的方法。先介绍一个时间前向独立集的其他例子。

这是一个DAG。所谓 DAG 就是有向无回路图。在 DAG 中的每一条边都是有方向的,但是 DAG 中不允许有环形的回路。

这个DAG 比较特殊,它的每一个源点,也就是没有指向它的边的节点都有一个逻辑变量值 0 或者 1。所有的中间节点上都有一种逻辑运算,其中 ∧是与运算, ∨是或运算。逻辑运算的计算方法你应该比较清楚了。在这个 DAG 中,我们希望求解所有的点上代表的逻辑变量值。比如某一个顶点 v 上面的运算是与运算,而指向它的两个逻辑变量值均为 1,那么顶点 v 所代表的逻辑变量值就是 1。依此类推。

解决这个问题的关键之一是,我们必须要知道按照什么顺序来计算这些点的逻辑变量值。如果当我们要计算一个点的值时,它的两个输入的值还没有求出来,那么这个点的值就无法求出来,需要等待前面的节点的值。所以,我们要先理解一个内存算法,叫作拓扑排序。

小可: 拓扑排序?

Mr. 王:是的,拓扑排序是一个非常经典的图算法,适用于 DAG,将 DAG 转化为一个序列。

首先我们来谈谈什么是拓扑排序。 你听说过课程网络图吧?

小可: 就是描述那些课程前置关系的有向图。比如要想学高等数学,就应该先学初等数学。在课程网络图中,就画一条有向边,由初等数学指向高等数学。

Mr. 王:嗯,这条边也就描述了两门课程的先后关系。在实际生活中,类似课程网络图这种具有先后关系的例子是非常多的。在课程网络图中,也经常会出现一些比较复杂的情况,比如两门课程同时是第三门课程的前置课程,如“ C 语言程序设计”和“计算机数学基础”这两门课程,都是“数据结构与算法”这门课程的前置课程。在实际的课程图中,这个网络会变得非常的庞大且复杂。这种网络也叫作 AOV 网。

小可:什么是 AOV 网?

Mr. 王:所谓AOV 网(Activity-On-Vertex network),就是顶点活动网。在这种网络中,我们用节点来代表一个活动(Activity),用有向边来表示它们之间的前置关系。在课程网络图中,这个Activity 代表的就是课程,它用图中的节点来表示,而用有向边来表示课程中的前置关系。比如有两个节点 A、 B,如果有一条边 (A,B) 就说明A 必须在 B 之前执行,或者说仅当 A 执行过之后, B 才能执行。 AOV 网具有这样一个特点,就是它是一个 DAG,也就是有向无回路图。

小可:嗯,如果有回路就不对了,“后面”的课程不可能重新成为“前面”的课程的前置。

这是符合逻辑的。

Mr. 王:没错,在 AOV 网中,就有一个关于你说的“前面”和“后面”的问题。我们想要排出一个各项任务的执行序列,也就是在实际的执行过程中,这些活动到底谁先执行,谁后执行,同时要使得它们不违背AOV 网所描述的前置关系。这项工作就叫作拓扑排序。

小可:在课程网络图中,求拓扑排序就相当于排出一个课程的顺序表吧,就是我先上哪一门课,再上哪一门课。这就像是通过课程网络图来编写课程培养计划一样。

Mr. 王:没错,现在我们来形式化这个问题。拓扑排序就是将像 AOV 网这样的 DAG 转换成一个线性序列,使得如果 AOV 网中存在一条边 (a,b),那么在形成的这个线性序列之中, a 就要出现在 b 的前面。

小可:这个问题还真的很有意义,可以用来排前面提到的课程顺序表。那么这个问题怎么解决呢?

Mr. 王:其实有一个非常简单易行的算法可以解决这个问题。

每一轮的迭代只需要完成三项工作 :

第一, 找到一个没有入度的顶点。

第二, 将它插入到拓扑序列中。

第三, 将它和它所有的出度从 AOV 网中删除。

小可:就这么简单?

Mr. 王:没错,就是这么简单。我们可以用刚才的图来举例。响其后置活动的执行。比如学过了“计算机数学基础”和“ C 语言程序设计”,就可以学习“数据结构与算法”了,所以我们可以将加入了拓扑序列的那些节点的出度删除,然后这个节点也就没用了,同样删掉。

小可:于是就会有更多的节点“露”出来,没有了入度,它们就可以被加入到拓扑序列中。我懂了,这个步骤可以持续执行下去,直到所有的活动都被加入到拓扑序列中。可是在每一个步骤中,如果发现有两个节点都没有入度怎么办呢?

Mr. 王:这种情况也是普遍存在的,在这种情况下任选一个或者取 ID 较小的那个节点就可以了。因为选择任何一个节点都不会破坏拓扑序列满足 AOV 网的要求。但这也意味着,拓扑序列是不唯一的。

小可:嗯,我懂得拓扑排序了。

内容来源:灯塔大数据

本文分享自微信公众号 - 灯塔大数据(DTbigdata)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-03-24

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 人工智能 |「凡是过往,皆为序章。」64岁的RODNEY BROOKS谈AI的起源与发展

    我们距离通用人工智能还有多远?这是一个很多人都在试图回答的问题。然而对于人工智能领域的真正从业者来说,我们面前的道路还很长。Rethink Robotics 创...

    灯塔大数据
  • 不寒而栗!国外创业公司从Facebook网页挖掘私密数据

    ? 这是我在Tenant Assured上报告最初的样子,里面搜集了我的Facebook、Twitter、LinkedIn和Instagram数据。我已经修改...

    灯塔大数据
  • 2016互联网全行业洞察及趋势报告(完整版)

    导读 中国互联网走过了将近30年历程,自身面貌发生了巨大变化。艾瑞十几年间持续观察、解读并见证了互联网的飞速发展。2016年互联网全行业洞察及趋势报告《润物有...

    灯塔大数据
  • VR也能在艺术展中这么玩,极强烈的艺术未来感

    VRPinea
  • 第十五届ChinaJoy今日盛大开幕,泛VR概念占了半壁江山

    VRPinea
  • 戛纳国际创意节的新宠:VR+品牌营销

    镁客网
  • “剪掉尾巴”的PC VR,会是VR的未来吗?

    镁客网
  • 玩转基因组浏览器之展示RNA_seq中的基因表达量

    CNV类似,IGV也可以以热图的形式展示基因表达量的数据,要求表达量文件的格式为gct, 示意如下

    生信修炼手册
  • 图嵌入方法介绍

    在现实世界的各种场景中,图处处可见。社交网络是在人与人构建连接的图,生物学家使用图描述蛋白质分子的交互,通信网络本身就以图的形式存在。在文本挖掘中还会使用词共现...

    AI研习社
  • 光有Gear VR不够,三星联合Nibiru布局VR一体机生态

    镁客网

扫码关注云+社区

领取腾讯云代金券