当前位置：文档之家› 数据结构之图结构的应用

数据结构之图结构的应用

数据结构DATA STRUCTURE, DS

授课教师：郭艳

:191124

授课班级: 191124

中国地质大学计算机学院

2014年春

上堂课要点回顾

图的应用一：最小生成树问题

定义

Prim算法及其实现

Kruskal算法

图的应用二：最短路径问题定义

单源最短路径问题

——Dijkstra算法(O(n2))

第十五次课

阅读：

朱战立，第235-242页

习题：

作业14

数据结构课程内容

图结构的应用3——拓扑排序

图结构的应用4——关键路径

9.7 拓扑排序（topological sort）

先决条件问题学生选修课程问题：

学生应按怎样的顺序数学模型：有向无环图顶点——活动（课程）

拓扑排序

将一个有向学习下列课程，才能

无矛盾、顺利地完成

有向弧——活动i

是活动j的先决条件

无环图中所有顶点在不学业？

课程

代号

课程名称先修课

C4C5

违反先决条件关系的前C1程序设计基础无

C2离散数学C1

C3数据结构C1,C2

C4汇编语言C1

语言的设计和分析C3C4

C1C3C7

提下排成线性序列的过C5C3,C4

C6计算机原理C11

C7编译原理C3.C5

C8操作系统C3,C6

C9C10

C12

程称为拓扑排序C9高等数学无

C10线性代数C9

C11普通物理C9

C1C9C10

C11Activity On

Vertex network C12数值分析C1,C9,C10

序列1：C1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12->C8

序列2：C9->C10->C11->C6->C1->C12->C4->C2->C3->C5->C7->C8

Vertex network

9.7 拓扑排序（续）

拓扑序列(topological order)

对于有向无环图G=(V, E), 所有顶点组成的

线性序列如果满足

若在有向无环图G中从顶点V i到V j有一条路径，

则在序列中顶点V必在顶点V之前

i j

则该线性序列可称作一个拓扑序列。

拓扑序列不唯一

9.7 拓扑排序（续）

任何有向无环图G的所有顶点都可以排在一个拓扑序列里。

拓扑排序的方法是：

1、从图G中选择一个入度为0的顶点并输

出。

2、从图G中删掉此顶点及其所有的出边。

3、回到第1步继续执行，直至G所有顶点

都被输出或G中不存在入度为0的顶点。

C4C5

C1C3C7 C12

C8 C9C10

C11

C4C5

C3C7C8

C12

C10C6

C10C11

C11

（1）拓扑序列：C1

（2）拓扑序列：C1->C2

C7C8

C12

C10C6

C10C11

C11

（3）拓扑序列：C1->C2->C3

（4）拓扑序列：C1->C2->C3->C4

C12

C6C8

C9C10

C11

（5）拓扑序列：C1->C2->C3->C4 ->C5（6）拓扑序列：C1->C2->C3->C4 ->C5->C7

C12

C10

C8 C6

C11

（7）拓扑序列：C1->C2->C3->C4 ->C5->C7->C9（8）拓扑序列：C1->C2->C3->C4 ->C5->C7->C9->C10

C12

（9）拓扑序列：C1->C2->C3->C4

->C5->C7->C9->C10->C11

（10）拓扑序列：C1->C2->C3->C4

->C5->C7->C9->C10->C11->C6

）拓扑序列）拓扑序列C1C2C3C4

（11）拓扑序列：C1->C2->C3->C4

->C5->C7->C9->C10->C11->C6->C12

（12）拓扑序列：C1->C2->C3->C4->C5->C7->C9->C10->C11->C6->C12->C8

拓扑排序算法首先需要计算各顶点的入度，然

后在拓扑排序过程中，当某个顶点的入度为零

时就将此顶点输出同时将该顶点的所有直时，就将此顶点输出，同时将该顶点的所有直接后继顶点的入度减1。为了避免重复检测入度为零的顶点，设立一个栈（或队列），以保度为零的顶点设立个栈或队列以保存当前所有“入度为零”的顶点

若有向G中所有顶点都被输出，则表明G中没有有向环，拓扑排序成功。若仅输出了部分顶

拓扑排序成功若仅输出了部分顶点，G中已不存在入度为0的顶点，则表明G中存在有向环，拓扑排序失败。

存在有向环拓扑排序失败

拓扑排序算法实现：设图G的顶点数为n采用邻接矩拓扑排序算法实现：设图G的顶点数为n，采用邻接矩

阵作为存储结构

1、对各顶点求入度

2、初始化栈S，初始拓扑序列长度计数器size=0

3、把所有入度为0的顶点入栈S

4、当栈S非空时循环

41输出栈顶元素v并出栈size++

4.1 输出栈顶元素v并出栈；size++；

4.2 获得所有与v邻接的未被访问的顶点w

4.3 把w的入度减1；

4.4 若w的入度为0则入栈S

直至栈空为止

5、如果size ≠ n，则有向图有环，不存在拓扑序列，拓扑

排序失败；否则，拓扑排序成功

6、结束

9.7 拓扑排序（续）

拓扑排序算法的时间复杂度分析

关键是算法在开始时要找出所有入度为

关键是，算法在开始时要找出所有入度为0

的顶点（同时可知道其它顶点的入度）

时算法在开始时找所有当采用邻接矩阵时，算法在开始时找所有

入度为0的顶点需要O (n2)的时间，加上

处理边、顶点的时间，总代价为

O(n2+e+n)= O (n2)

()(

当采用邻接表时，因为在顶点表的每个顶

点中可以有一个字段来存储入度，所以算

点中可以有个字段来所以算

法在开始时找所有入度为0的顶点只需要

O(e)的时间，加上处理边、顶点的时间

，总代价为O(n+2e)=O(n+e)

9.8 关键路径

工程计划有关问题

把工程计划表示为有向无环图G ，用顶点表示事件，弧表示活动权表示活动持续时间动，权表示活动持续时间

。每个事件表示在它之前的活动已完成，在它之后的活动可以开始（约束条件）

例：设一个工程有m =11项活动，n =9个事件，其中事件v j 事件v1——表示整个工程开始(记为v)事件v9——表示整个工程结束(记为vn)表示其持续时间记为d t ()

活动a i 用弧表示，其持续时间记为dut ()问题：（1）完成整项工程至少需要多少时间？

（2）哪些活动是影响工程进度的关键活动？

64a6=2

定义1

(Activity On Edge network, AOE 网(Activity On Edge network, 边表示活动的网)是一个顶点表示事件，弧表示活动，权表示活动持的带权有向无环图。网中仅存在一个入度为续时间的带权有向无环图。网中仅存在个入度为0的顶点，称作开始顶点；网中仅存在一个出度为0的顶点，称为结束顶点

距离——路径上各活动持续时间之和

关键路径——从开始顶点到结束顶点的距离最长的路径

由于网中某些活动可以同时进行

AOE 网中某些活动可以同时进行，要保证每个活动都能无矛盾顺利完成(约束条件)，完成该工程的最少时间

72就是该工程AOE 网的

关键路径距离。98

43a6=2

定义2(j)—— Ve (j)表示事件vj 的最早(early)发生时间，是从开始顶点v 到vj 的最长路径距离。其中Ve(n)是该工程AOE 网的关键路径距离。?如何计算

616

187

Ve 示例6

Vl 示例9

4a6=2576

4a6=2810

Vl (j)——表示事件vj 的最迟(last)发生时间，是在不

推迟整个工程完成(即保证结束顶点vn 在Ve(n)时刻发生)的前提下,该事件最迟必须发生的时间。

Vl (j)=Ve(n)的最长路径距离

(j)=Ve(n) －顶点vj 到结束顶点vn 的最长路径距离。？如何计算

(i)—— e (i)表示活动ai 的最早(early)开始时间，是该活动的起点所表示事件的最早发生时间

如果边则有

表示活动ai ，则有e(i)=Ve(j)

727206716e 示例06716l 示例616186

161898

198

14076720471406

146

4a6=2

5714

81014

57810

l (i)——表示活动ai 的最迟(last)开始时间，是该活动

的终点所表示事件的最迟发生时间与该活动的所需时间之差

i 则有(i)Vl(k)d t()

如果边表示活动ai ，则有l (i)=Vl(k)-dut()

(i)-e(i)—— l (i)e(i)表示完成活动ai 的时间余量，它是在不增加完成整个工程所需时间的情况下，活动ai 可以拖延的时间

关键活动——关键路径上的活动，即l (i)=e(i)的活动

计算计算7

067

e 06716

l 9

a6=2

64a6=2

810

3a6=2