Video慕课视频播放-数据结构（Data Structures）-MOOC慕课视频教程-柠檬大学

各位同学大家好

在这节课中

我们将学习到针对

有向图的顶点的一种排序操作

拓扑排序操作

拓扑排序它的问题背景

在日常生活中

有时候我们要完成一组任务

而这些任务之间

又存在一些先决条件的约束

有些任务

它的执行必须要优先于

其它某些任务

如果我们把这些任务

以及它们彼此之间的关系

用一张有向图来去表示

那么每个任务

就对应图中的一个顶点

这个有方向的连边

表示任务执行的先后关系

比如在这个例子中

任务J1它是J2和J3的先决条件

那么J1就必须要先于J2和J3来完成

类似的J2是J4 J5 J6的先决条件

那么给定这样的一组任务

我们的问题是

如何去安排一个合理的

任务的执行次序

使得在不违反任务之间的

先后次序的前提下

能够完成这些任务

比如在这个例子中

我们可以先去执行J1

然后是J3

接着执行J2 J6 J4 J5 J7

这个对有向图中的顶点

进行排序的过程

我们称为叫拓扑排序

得到的序列叫拓扑排序序列

拓扑排序问题是一个常见的问题

比如说

同学们在选课的时候

就会遇到这个问题

选课的时候我们面临的是

这样的一张课表

课程之间它存在着先后关系

比如我们在学习数据结构之前

应该要先去学习

C1和C2这两门课程

也就是程序设计基础和离散数学

根据这些课程的先后关系

我们会得到一张对应的有向图

图中的顶点是每门课程

反应了课程之间的先后关系

比如只有当C1和C2都上完了

我们才能去学习C3这门课

那么要得到一个合理的选课次序

实质上就是要对这个有向图

来进行一个拓扑排序

得到一个符合图中所刻画的

这个先后关系的顶点序列

我们可以看到

这里面我们可以先学习C1

然后C2

然后是C3 C4 C5 C7 C9 C10

C11 C6 C12 C8

这是一个拓扑排序的序列

当然这个序列它并不是唯一的

下面这个序列

同样也是拓扑排序序列

所以排序的序列它是不唯一的

而且除了这两个序列之外

还应该有更多的

其它拓扑排序的序列

那么这些序列有哪些共同的特征呢

什么样的顶点应该排在前面呢

这是我们要思考的问题

如果我们要按照拓扑排序序列

逐个说出图中的顶点

那么可以优先输出的顶点

应当是那些没有先决条件的顶点

也就是说没有边指向它们的顶点

比如在这个图中的J1

在图论里面有一个关于入度的定义

一个顶点它的入度

等于指向它的连边的数目

所以拓扑排序中

能够优先输出的顶点就是

这些入度为0的顶点

当我们输出顶点J1之后

代表的J1这个任务已经完成了

它对其它任务的约束

就应该可以取消掉

比如这里以J1

作为先决条件的J2和J3

我们可以取消掉J1对它们的约束

对应地我们应该让

J2和J3它们的入度减少1

这个时候

图中的入度为0的顶点就有J2和J3

我们可以任意选择其中的一个

比如我们选择J2

那么输出J2之后

我们接着去取消J2

对其它顶点的约束

所以我们可以对每个

从J2出发的连边

将另连边外一个顶点的入度减1

所以J4 J5 J6

它们的入度都要减少1

然后我们继续从中选择一个0入度的顶点

来进行输出

如此反复

直到图中找不到0入度的顶点

所以整个拓扑排序的过程

都是围绕着顶点的入度来展开的

输出的只能是0入度的顶点

输出一个顶点之后

又会对其它顶点的入度构成影响

然后再次输出0入度的顶点

如此反复

下面我们来通过一段伪代码

来总体刻画一下

拓扑排序算法的主要过程

为了进行拓扑排序

我们首先要计算图中

每一个顶点它的入度

然后从中我们要选择一个0入度的顶点v

并且输出这个顶点

在输出之后

我们要取消v对于其它顶点的约束

所以对从v出发的每条连边v到w

我们将连边的另外一个顶点w

它的入度减少1

然后我们继续循环上面的过程

直到图中没有0入度的顶点

上面这个过程中标红色的这个步骤

需要在每次循环的时候

从图里面选择一个0入度的顶点

这需要去检查所有顶点的入度

然后从中进行选择

效率是比较低下的

这就好比

我们每次都要在整个书架里面

去找某一本书来看

这个消耗的时间是比较多的

如果我们能够把我们需要的东西

先收集起来放到一个容器里面

那么取东西的时候就要高效的多

所以这里面我们可以采用一个容器

去记录这些0入度的顶点

从而避免频繁的查找过程

所以我们在算法开始的时候

在统计完顶点的入度之后

我们把0入度的顶点

先放入到一个容器中去

这个容器可以是队列栈

或者是任何其它

能够存储一种元素的数据结构

我们这里所采用的是队列Q

这样只要队列它不是空的

我们就可以执行下面的过程

每次从中选择一个0入度的顶点

它就比较方便了

直接从Q中取出一个顶点v

然后可以输出v

并且我们对每条

从v出发的连边v到w

给w的入度减1

如果这个时候

w的入度也变成0了

那么我们再将w

放入到队列中去

通过这种方式

得到图中0入度的顶点

因为它们始终都存储在这个队列Q中

最后我们来看一下

拓扑排序的具体代码实现

这里所实现的拓扑排序函数

有两个参数

一个是图的指针G

一个是辅助计算的队列指针Q

这个队列用来去记录0入度的顶点

首先我们定义一个数组indgree

用来去记录顶点的入度

然后我们将这些顶点的入度

都初始化为0

接下来我们将统计每个顶点的入度

我们所采用的是两重for循环

这些语句的具体含义是

对于图中的每一个顶点v

对于v的每个邻居w

应该存在一条v到w的连边

所以我们给w它的入度加1

当循环结束的时候

indgree里面记录的

就是每一个顶点的入度

统计完入度之后

我们将0入度的顶点收集起来

这里成一个for循环来实现

对于图中的每一个顶点v

如果它的入度等于0

我们就把它加入到队列Q中去

接下来是个循环输出

0入度顶点的过程

只需要队列它不是空的

也就是说这里面还有0入度顶点的话

我们将执行下面的过程

每次我们从队列中

取出一个0入度的顶点v

然后打印输出

接着我们将取消v

对于图中其它顶点所构成的约束

这是通过一个循环语句来实现的

对v的每个邻居w

对于一条从v出发到w的连边

我们要取消v对w

所构成的先决条件的约束

所以这里我们给w它的入度减1

如果这个时候w入度变成0了

那么我们就要把w加入到队列Q中去

这样可以让这个队列Q始终是保存着

图中所有0入度的顶点

循环不断地执行

直到队列变成空的

图中不再存在0入度的顶点

这个时候

拓扑排序就结束了

好的

这节课我们就讲到这里

下节课我们再见

数据结构（Data Structures）课程列表：

1. Introduction

-1. Introduction--1.1 Introduction of Data

-1.1 Introduction of Data Structure

--Introduction of Data Structure

-1.2 Data Structure and A

-1.2 Data Structure and Algorithm

--Video

-1.3 Asymptotic Analysis

--Video

-1.4 Simplifying Rules of

-1.4 Simplifying Rules of Asymptotic Analysis

--Video

2. List

-2.1 Introduction of List

--Video

-2.2 Array based List

--Video

-2.3 Insertion Operation on Array

-2.3 Insertion Operation on Array based List

--Video

-2.4 Remove Operation on Array based List

--Video

-2.5 Linked list

--Video

-2.6 Insertion Operation on Linked list

--Video

-2.7 Remove Operation on Linked list

--Video

-2.8 SetPos Operation on Linked list

--Video

-2.9 Stack

--Video

-2.10 Application of Stack

--Video

-2.11 Queue

--Video

3. Tree

-3.1 Definition of Binary Tree

--Video

-3.2 Implementation of Binary Tree

--Video

-3.3Traversal

-3.3 Traversal

--Video

-3.4 Binary Search Tree

--Video

-3.5 Search on BST

--Video

-3.6 Insertion on BST

--Video

-3.7 Introduction of Heap

--Video

-3.8 Construction of Heap

--Video

-3.9 Operations on Heap

--Video

-3.10 General Tree

--Video

4. Search

-4.1 Definition of Searching

--Video

-4.2 Searching of Sorted Array

--Video

-4.3 Definition of Hash Table

--Video

-4.4 Collision in Hash Table

--Video

-4.5 Extension of Linear Probing

--Video

-4.6 Insertion Operation of Hash Table

--Video

-4.7 Search Operation of Hash Table

--Video

5. Index

-5.1 Introduction of Index

--Video

-5.2 Linear Index

--Video

-5.3 2-3 tree index

--Video

-5.4 Implementation of 2-3 tree

--Video

-5.5 B-Tree

--Video

-5.6 Insertion Operation on B+ Tree

--Video

-5.7 Deletion Operation on B+ Tree

--Video

6. Graph

-6.1 Definition of Graph

--Video

-6.2 Implementation of Graph

--Video

-6.3 Adjacency Matrix

--Video

-6.4 Adjacency List

--Video

-6.5 Graph Traversal - DFS

--Video

-6.6 Graph Traversal - BFS

--Video

-6.7 Topological Sort

--Video

-6.8 Shortest Path Problem

--Video

-6.9 Single Source Shortest Path

--Video

-6.10 Dijkstra Algorithm

--Video

7. Sorting

-7.1 Sorting Problem

--Video

-7.2 Insertion Sort

--Video

-7.3 Selection Sort

--Video

-7.4 Bubble Sort

--Video

-7.5 Shell Sort

--Video

-7.6 Quick Sort

--Video

-7.7 Heap Sort

--Video

-7.8 Comparison

--Video

Video在线视频

Video

Video课程教案、知识点、字幕

数据结构（Data Structures）课程列表：

1. Introduction

2. List

3. Tree

4. Search

5. Index

6. Graph

7. Sorting

Video笔记与讨论

也许你还感兴趣的课程: