拓扑序列： c1 c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
v4 v3
2
1
3 ^
5
4
v5
3
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 0 1 0 2 0 3 1 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
v4 v3
2
2
3
5
4
v5
v6
0 1 2 3 4 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
一、定义
一个无环的有向图称为有向无环图，简写为 DAG（directed acycline graph）。 与有向二叉树相比，有向无环图是更一般的特 殊有向图。 实例：
有向树
有向无环图
有向图
教材179页给出了有向无环图的一个简单应用： 用有向无环图描述算术表达式。
二、拓扑排序
1.引例：现有计算机课程12门，如下表所示：
c11
c10
c8
二、拓扑排序
3.方法：
c4 c5 c2 c1 c3 c7
c12 c9 c10 c8
c6 c11
拓扑序列： c1 c2 c3 c4 c5 c7 c9 c10 c11 c6 c12 c8
二、拓扑排序
3.方法： 注意1：从某种意义下来说，拓扑排序的结果是不 唯一的。 注意2：这种以顶点表示活动的有向无环图称为活 动在顶点的网，简称AOV(Activity On Vertex Network)网。
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 0 1 0 2 0 3 1 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
v4 v3
2
2 3
5
4
v5
v6
4号、1号顶点的入 另外增设一个存放各顶点的入度值的一维数组 indegree: 度分别减1
indegree[0..5] 0 0 1 1 0 2 0 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
c6
c9
c3,c6 无 c9 c9 c9,c10,c1
二、拓扑排序
2.拓扑排序：
c4 c5 c2 c1 c3 c7
c12 c9 c10 c8
c6 c11
偏序是指集合中仅有部分元素可比较大小(或先后)；
全序是指集合中所有元素均可比较大小（或先后）。
二、拓扑排序
2.拓扑排序：
c4 c5 c2 c1 c3 c7
0
v1
v2
1
s
3
v4 v3
2
5
4
v5
3
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 0 1 0 2 0 3 1 4 0 5
二、拓扑排序
4号顶点的入度减1 4.算法说明：为了使说明过程简单起见，我们以下 图为例： 打印G.vertices[3].data
0
v1
v2
1
s
3
v4 v3
2
2
3
5
4
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 1 1 0 2 0 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例： 打印G.vertices[2].data
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^
3
v4
v3
2
5 0
5
4
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5
0
v1
v2
1
s
3
v4 v3
2
5
4
v5
0
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 1 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例： 打印G.vertices[0].data
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ 4 4 ^ 1 ^ 3 2 1 ^
0
v1
v2
1
s
3
vቤተ መጻሕፍቲ ባይዱ v3
2
3号、2号、1号顶 G.vertices[5] v6 4 点的入度分别减1
indegree[0..5] 0 0 2 1 1 2 1 3
5
3 ^
4
v5
0
0 5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
2 4
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 1 1 0 2 0 3 2 4 0 5
二、拓扑排序
4.算法说明：为了使说明过程简单起见，我们以下 图为例：
G.vertices[0] v1 G.vertices[1] v2 ^ G.vertices[2] v3 G.vertices[3] v4 G.vertices[4] v5 ^ G.vertices[5] v6 4 3 ^ 4 4 ^ 1 ^ 3 2 1 ^
data
firstarc
adjvex nextarc
0
v1
v2
1
3
v4
v3
2
5
4
v5
v6
另外增设一个存放各顶点的入度值的一维数组indegree:
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5
二、拓扑排序
indegree一维数组初值的程序： 4.求 算法说明：为了使说明过程简单起见，我们以下 FindInDegree(ALGraph G,indegree[0..G.vexnum-1]{ 图为例：
课程编号
c4
课程名称
c2
c5
先修课程
c1
c1
程序设计基础
离散数学 数据结构 c3 汇编语言
无
c1 c1,c2 c1 c3,c4 c11 c5,c3
c8 c7
c2 c3 c4 c5 c6 c7 c8 c9 c10 c11 c12
c11 c10
语言的设计和分析 c12 计算机组成原理 编译原理 操作系统 高等数学 线性代数 普通物理 数值分析
indegree[0..5] 0 0 2 1 1 2 2 3 3 4 0 5