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

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

非主流自然语言处理:大规模语料词库自动生成

一、前言   写这篇文时,突然想到一个问题,大家的词库都是从哪来的?   之所以会这么有些意外的问,是因为从没把词库当成个事儿:平时处理微博,就用程序跑一下微博...

67312
来自专栏深度学习思考者

最短路径(一)——多源最短路径

引出问题:多源最短路径的问题 暑假,小文准备去一些城市旅游。为了节省经费以及方便计划旅程,小文希望知道任意两个城市之间的最短路径。假如有四个城市八条公路。 我们...

22110
来自专栏算法channel

AI 路上,第一步这么走下去...

算法是描述解决一个问题的步骤,外界给它所指定的数据,然后经过一系列步骤输出一个结果。为了更快更轻量级地解决问题,我们会选择高效精简的结构去实现,这种结构称为数据...

1266
来自专栏小红豆的数据分析

小蛇学python(2)两百行代码实现旅游中国34座大城市最短路径

直接说基础语法,也许大家不会感兴趣。前言之后的这一章,给大家介绍一下我最近写出来的一个小功能。用python语言实现GA算法来解决TSP问题,希望以此来激发大家...

2894
来自专栏苦逼的码农

动态规划进阶篇1---背包问题

给定n种物品和一背包。物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品,使得装 入背包中物品的总价值最大?

1.8K3
来自专栏程序员的知识天地

Python入门操作-时间序列分析

时间序列(或称动态数列)是指将同一统计指标的数值按其发生的时间先后顺序排列而成的数列。时间序列分析的主要目的是根据已有的历史数据对未来进行预测。本文我们会分享如...

2252
来自专栏趣学算法

ACM竞赛学习指南(算法工程师成长计划)

7641
来自专栏懒人开发

(7.7)James Stewart Calculus 5th Edition:Approximate Integration

黎曼求和,我们把对应的[a, b]分成n份,每份大概为 Δx = (b - a)/n 这个时候,有:

1843
来自专栏一个会写诗的程序员的博客

函数式编程与面向对象编程[3]:Scala的OOP-FP混合式编程与抽象代数理论

Scala是纯种的面向对象的语言。从概念上讲,每一个值都是一个对象,每一个操作都是一个方法调用。语言支持通过类和特征的高级组件架构。

1292
来自专栏take time, save time

编程一样可以很带感--1+1不一定等于“2”

刚玩了两把flash小游戏,我也不知道为什么我从小就喜欢玩这个东西,想当初我上大学选软件的目的就是为了学会做flash,那时目的单纯吧?哈哈,初中的时候看的...

3696

扫码关注云+社区

领取腾讯云代金券