LOGO
C8
C1 C3
C9 C7
C4
C2
C6
C5
2020/9/17
.
7
检测有向环的方法——拓扑排序
LOGO
检测有向环的一种方法是对AOV网络构造它的拓扑有 序序列。
——即将各个顶点 （代表各个活动）排列成一个线性 有序的序列，使得AOV网络中所有应存在的前驱和后继 关系都能得到满足。
这种构造AOV网络全部顶点的拓扑有序序列的运算就 叫做拓扑排序。
2020/9/17
.
LOGO
13
数据结构的选择
LOGO
输出序列V：用一维数组来描述;
用一个栈来保存加入V的候选顶点；
另有一个一维数组InDegree，InDegree[j]表示与 顶点j相连的节点i的数目，其中顶点i不是V中的成员， 它们之间的有向图的边表示为（i，j）。
2020/9/17
.
C1
C2
C1
C2
C3
2020/9/17
C5
C3
.
C5
10
拓扑排序的过程（续）
LOGO
C1
C2
C1
C5
C5
C5
最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。满足 图中给出的所有前驱和后继关系，对于本来没有这种关系的顶 点，如C4和C2，也排出了先后次序关系。
2020/9/17
▪ Kruskal算法 ▪ Prime算法 ▪ Sollin算法
2020/9/17
.
3
1、拓扑排序
LOGO
❖ DAG图：有向无环图 ❖ 几乎所有的工程（project）都可分为若干个称作
“活动”的子工程，并且这些子工程之间通常受 着一定条件的约束，例如其中某些子工程必须在 另一些子工程完成之后才能开始
InDegree[u]--;
if (!InDegree[u]) S.Add(u);
u = NextVertex(w);
}
} 2020/9/17
.
DeactivatePos(); delete [] InDegree; return (i == n); }
邻接矩阵：Θ(n2) 邻接链表：Θ(n+e)
16
Chapter13 贪婪算法
LOGO
2020/9/17
.
1
内容提要
❖13.1 示例问题提出 ❖13.2 贪婪算法的思想 ❖13.3 贪婪算法的应用
▪ 货箱装船 ▪ 拓扑排序 ▪ 单源最短路径 ▪ 最小耗费生成树
2020/9/17
.
LOGO
2
贪婪算法应用
LOGO
❖拓扑排序 ❖单源点最短路径——Dijkstra算法 ❖最小耗费生成树
❖ 对整个工程和系统，主要关心两方面的问题：
▪ 工程能否顺利进行——拓扑排序；
▪ 完成整个工程所必须的最短时间——求关键路 径
2020/9/17
.
4
顶点表示活动的网络 (Activity On Vertices: AOV 网络) LOGO
用有向图表示一个工程。在这种有向图中， • 用顶点表示活动， • 有向边<Vi, Vj>表示活动Vi 必须先于活动Vj 进行。 —— 顶点表示活动的网络(Activity On Vertices)， AOV 网络。
14
bool Network::Topological(int v[]) {
LOGO
int n = Vertices();
int *InDegree = new int [n+1]; InitializePos(); for (int i = 1; i <= n; i++) InDegree[i] = 0;
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成； 或图中还有未输出的顶点，但已跳出处理循环——这说明图 中还剩下一些顶点，它们都有直接前驱，再也找不到没有前 驱的顶点了。这时AOV网络中必定存在有向环。
2020/9/17
.
9
拓扑排序的过程
LOGO
C0
C1
C2
C0
C1
C2
C3
C4
C5
C3
C4
C5
C0
如果通过拓扑排序能将AOV网络的所有顶点都排入一 个拓扑有序的序列中，则该AOV网络中必定不会出现有向 环；反之，说明AOV网络存在有向环，工程不可行。
2020/9/17
.
8
拓扑排序方法
（1）输入AOV网络。令 n 为顶点个数。
LOGO
（2）在AOV网络中选一个没有直接前驱的顶点， 并输出之；
（3）从图中删去该顶点， 同时删去所有它发出的有向边； 重复以上（2）、（3）步, 直到
.
11
课堂练习：学生选课的拓扑序列
C8
C1 C3
C9 C7
C4
C2
C6
C5
LOGO
2020/9/17
.
12
拓扑排序用贪婪算法实现
设n是有向图中的顶点数 设V是一个空序列 while(true) {
设w不存在入边（v,w），其中顶点v不在V中 如果没有这样的w，break。 把w添加到V的尾部 } if(V中的顶点个数少于n)算法失败 else V是一个拓扑序列
for (i = 1; i <= n; i++) 首先计算每个顶点的入度
{
int u = Begin(i);
while (u) {
InDegree[u]++;
邻接矩阵：Θ(n2) 邻接链表：Θ(n+e)
20/9/17
.
15
LinkedStack<int> S;
课程代号
C1 C2 C3 C4 C5 C6 C7 C8 C9
课程名称 高等数学 程序设计基础 离散数学 数据结构 高级语言程序设计 编译方法 操作系统 普通物理 计算机原理
先修课程
C1, C2 C3, C2 C2 C5, C4 C4, C9 C1 C8
2020/9/17
.
LOGO
6
表示课程之间优先关系的有向图
补充：AOE网络
LOGO
❖用边表示活动的网络
在AOV网络中，如果活动Vi 必须在活动Vj 之前进行，则 存在有向边<Vi, Vj>， AOV网络中不能出现有向回路，即有 向环。
在AOV网络中如果出现了有向环，则意味着某项活动应 以自己作为先决条件。
对给定的AOV网络，必须先判断它是否存在有向环。
2020/9/17
.
5
AOV 网络示例：选课问题
for (i = 1; i <= n; i++) if (!InDegree[i]) S.Add(i); 入度为0的顶点入栈
LOGO
i = 0;
while (!S.IsEmpty())
{
int w;
S.Delete(w);
v[i++] = w;
int u = Begin(w);
while (u)
{ 删除并修改关联顶点的入度