顶点表示课程
有向弧表示先决条件
若课程i是课程j的先决条件
则图中有弧<i,j>
拓扑排序
应怎样学习这些课程，才能顺 把AOV网络中各顶点
利完成学业?
按照它们之间的先后
关系排列成一个线性
序列的过程
拓扑序列
广东石油化工学院 理学院
23
拓扑排序的过程
C0
C1
C2
C3
C4
C5
有向无环图
在邻接表的表头结点增加存放顶点入度的域
栈存放入度为零的顶点
v1
0
v2
2
v3
1
v4
2
v5
3
v6
0
4
3
2
5
2
5
5
4
拓扑序列：1 6 4 3 2 5
广东石油化工学院 理学院
27 27
AOV网 顶点表示活动的网 顶点表示活动，弧表示活动间的先后关系 AOV网中不允许有回路，这意味着某项活动以 自己为先决条件
广东石油化工学院 理学院
21
C4
C5
C2
C1
C3
C7
C12 C8
C9
C10
C6
C11
死锁？
课程代号 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12
V2
V3
V4 V5 V6 V7
V8
V1
V2
V3
V4 V5 V6 V7
V8 广度优先生成树
广东石油化工学院 理学院
11
非连通图的生成森林
非连通图，每个连通分量中的顶点集和遍历时走
过的边一起构成若干棵生成树
这些连通分量的生成树组成非连通图的生成森林
A
CD
F
G
I J
L
B E H K
M
A
D
LCF
E
15
最小生成树(Prim)算法
方法 设N=(V，E)是连通网，T=(U，E‘)是正在构造中的生成树 初始时，生成树只有一个结点，没有边
U={u0}，E’={ }，u0是任意选定的顶点， 从初始状态开始重复执行下列的操作
在所有u∈U，v∈V-U的边(u，v)，(u，v)∈E中找一条 代价最小的边(u‘，v’)并入集合E‘，同时V’并入集合U， 直到V=U为止。
visited[v]=1;
queue.clear();
queue.add(v);
while(!queue.isEmpty()){
v=queue.poll();//队头元素v出队列
Arcnode p=graph[v].getFirstArc();
while(p!=null){
w=p.getAdjvex();
if(visited[w]==0){
System.out.print("访问顶点"+w+" ");
visited[w]=1;
queue.add(w);//顶点w进队列Q
}
p=p.getNextArc();
}
}
}
队列
V1
V2
V3
V4 V5 V6 V7
V8
广东石油化工学院 理学院
88
图的连通性
怎样求图的连通分量？
在带权无向完全图中，访问每个顶点恰好一次、并且返 回出发点、总权数最小的回路
适合稠密图
广东石油化工学院 理学院
14
普里姆(Prim)算法最小生成树的过程
28
01
10 14 16
562
25 24 18 12
4 22 3
01
10 14 16
562
25 4
12
3
22
原图
(a)
广东石油化工学院 理学院
如此重复，直到所有顶点均被访问过为止 V1
public static void dfs(Vexnode[] graph,int v,int[] visited){
Arcnode p;
System.out.print(“访问顶点”+v+“ ”);
V2
visited[v]=1;//表示被访问
p=graph[v].getFirstArc();
广东石油化工学院 理学院
25
拓扑排序的方法
从有向图中任选一个入度为0的顶点，并访问 删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已访问，或当
图中不存在度为0的顶点为止 不存在度为0的顶点: 存在环
弧头顶点的入度减1
广东石油化工学院 理学院
26
构造拓扑排序的存储结构
AOV网用邻接表存储
广东石油化工学院 理学院
18
练习题
615
2
1
5
5
4
3 36
5
2
(Prim)算法
1
2
1
4
5
3 3
5
2
广东石油化工学院 理学院
19
克鲁斯卡尔(Kruskal)算法
A 6
B 14 12
D 14
15 F
8
C 17
E 5
6A8
B 14
C
12
D
E
F5
广东石油化工学院 理学院
20
有向无环图有关概念
无环图（DAG） 一个无环（回路）的有向图叫做有向无环图 directed acycline graph
算法 时间复杂度为o(n2)，其中n为网中顶点的个数 Prim算法适用于求边稠密的网的最小生成树
广东石油化工学院 理学院
16
克鲁斯卡尔算法构造最小生成树的过程
适合简单图
28
01
01
10 14 16
5 6 25 6 2
25 24
18 12
43
43
22
原图
(a)
广东石油化工学院 理学院
01
C0
C1
C2
C4 C0 C3 C2 C1 C5
C3
C4
C5
广东石油化工学院 理学院
24
拓扑排序举例
一个AOV网的拓
扑序列不是唯一的
C4 C2 C1 C12
C9 C10
C5
C3
C7
C8 C6
C11
拓扑序列： C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或： C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8
第14讲 图的遍历及应用 －－－－（最小生成树和拓扑排序）
广东石油化工学院 理学院
1
图的遍历
从图中某顶点出发,沿一些边访问图中顶点,使每个 顶点都被访问到，且仅被访问一次,叫做图的遍历
无重复，无遗漏 关键点
图中可能存在回路
图的顶点可能与其它顶点相通,在访问完某顶点后,可能沿 着某些边回到曾经访问过的顶点
while(p!=null) {
V4 V5
if(visited[p.getAdjvex()]==0)//没有访问过
dfs(graph,p.getAdjvex(),visited);
p=p.getNextArc();
V8
}
}
visited
v1
v2
v3
v4
v5
v6
v7
0
0
0
0
0
00Βιβλιοθήκη V3V6V7
v8 0
广东石油化工学院 理学院
广东石油化工学院 理学院
课程名称 程序设计基础
离散数学 数据结构 汇编语言 算法分析与设计 计算机原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析
先修课 无 C1
C1，C2 C1
C3，C4 C11
C3，C5 C3，C6
无 C9 C9 C1，C9，C10
22
拓扑排序
问题提出
选修课程问题
为避免重复访问,可设辅助数组visited[]
将其初始化为0 遍历时,如果某顶点 i 被访问,将 visited [i]置 为1 以此防止顶点i被多次访问
广东石油化工学院 理学院
2
图的深度优先搜索(DFS)
广东石油化工学院 理学院
3
图的深度优先搜索(DFS)
DFS:V1 V2 V4 V8 V5 V3 V6 V7
广东石油化工学院 理学院
10
V1
V2
V3
深度遍历： V1 V2 V4 V8 V5 V3 V6 V7
广度遍历： V1 V2 V3 V4 V5 V6 V7 V8
V4 V5 V6 V7
V1
V8
V1
V2
V3
V1
V2
V3
V4
V6
V4 V5 V6 V7 V8
V7
V8
V5
深度优先生成树
M JB
深度优先生成森林
G
K
I
H
广东石油化工学院 理学院
12 12
最小生成树
问题提出 在n个城市间建立通信网络
顶点—表示城市 权—城市间建立通信线路所需
花费代价
1
7
2
13
7 9
5
5 6
24
17
10 12
3
18
4
希望找到一条路径，使建立该 通信网所需花费的总代价最小
路径上各边权值的和最小
图的广度优先搜索算法