1北京邮电大学自动化学院
第 7章 图
? 7.1 图的定义和术语
? 1、图、顶点、边
? 图 G是由集合 V(G)和 E(G)组成,记为 G=(V,E)，其中 V(G)是顶
点的非空有限集合,E(G)是边的有限集合，边是点的无序对
或有序对。
? 2,有向图、弧、无向图
2 4 5
1 3 6
G1
? 若图中的边是顶点的有序对，则称此图为 有向图。
? 有向边又称为 弧,通常用尖括号表示一条有向边,<v,w>表
示从顶点 v到 w顶点的一条弧,v称为边的始点（或 弧尾 ）,w
称 为边的终点（或 弧头 ）。
2北京邮电大学自动化学院
例
2 4 5
1 3 6
G1
? 图 G1中,V(G1)={1,2,3,4,5,6}
? E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}
例
1 5 7
3 2 4
G2
6
? 图 G2中,V(G2)={1,2,3,4,5,6,7}
? 无向图 若图中的边是顶点的无序对，则称此图为 无向图 。通
常用园括号表示 无向边 。 （ v,w） 或（ w,v),并且（ v,w)=(w,v)
7.1 图的定义和术语
? E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
3北京邮电大学自动化学院
? 3、有向完全图、无向完全图
? 4、相邻顶点、相关联弧或边
? 无向完全图, n个顶点的无向图最大边数是 n(n-1)/2，具有
n(n-1)/2条边的无向图称为无向完全图。
2
1 3
有向完全图
2
1 3
无向完全图
7.1 图的定义和术语
? 若 <V1,V2> ?E或 (V1,V2) ?E,则 V1,V2是 相邻顶点,弧
<V1,V2>或边 (V1,V2)是与顶点 V1和 V2相关联弧或边 。
? 有向完 全 图,具有 n(n-1)条弧的有向图称为有向完全图。
4北京邮电大学自动化学院
? 5、度
例 1
2 4 5
1 3 6
G1
? 顶点 2入度,1 出度,3
? 顶点 4入度,1 出度,0
例 2
1 5 7
3 2 4
G2
6
? 顶点 5的度,3
? 顶点 2的度,4
7.1 图的定义和术语
? 一个顶点 V的度是与该顶点相关联的边的数目，记为 TD（ V）。
? 对于有向图，则把以顶点 V为弧尾的数目称为点 V的出度，
记为 OD（ V），把以顶点 V为头的弧的数目称为顶点 V的入
度，记为 ID（ V）。 顶点 V的度为：
?TD（ V） =ID（ V） +OD（ V）
5北京邮电大学自动化学院
? 6、子图
? 设有两个图 G＝ (V,E) 和 G‘＝ (V’,E‘)。若 V’? V 且
E‘?E,则称 图 G’ 是 图 G 的子图。
7.1 图的定义和术语
6北京邮电大学自动化学院
? 7、路径
? 若一条路径上除了 vi 和 vj 可以相同外,其余顶点均不相同，则
称此路径为一条 简单路径 。
7.1 图的定义和术语
? 在无向图 G＝ (V,E) 中,若存在一个顶点序列 vp1,vp2,…,v pm，
使得 (vi,vp1),(vp1,vp2),...,(vpm,vj)均属于 E，则称顶点 vi到 vj
存在一 条路径。 路径长度定义为路径上边或弧的数目。
? 起点和终点相同的路径称为 简单回路或简单环 。
7北京邮电大学自动化学院
例 2
1 5 7
3 2 4
G2
6
例 1
2 4 5
1 3 6
G1
? 路径,1,2,3,5,6,3
? 路径,1,2,5,7,6,5,2,3
7.1 图的定义和术语
? 路径长度,5
? 简单路径,1,2,3,5
? 回路,1,2,3,5,6,3,1
? 简单回路,3,5,6,3
? 路径长度,7
? 简单路径,1,2,5,7,6
? 回路,1,2,5,7,6,5,2,1
? 简单回路,1,2,3,1
8北京邮电大学自动化学院
? 8、图的连通 在无向图 G中，若两个顶点 vi和 vj之间有路径存
在，则称 vi 和 vj 是连通的。 若 G中任意两个顶点都是连通的，
则称 G为连通图。
连通图
例
2 4 5
1 3 6
强连通图
3
5
6
例例 2 4 5
1 3 6
非连通图，连通分量
? 9、强连通图与强连通分量 在有向图中,若对于每一对顶点 vi
和 vj,都存在一条从 vi到 vj和从 vj到 vi的路径,则称此图是 强连通
图 。非强连通图的极大强连通子图叫做强连通分量。
7.1 图的定义和术语
? 非连通图的极大连通子图叫做 连通分量 。
9北京邮电大学自动化学院
?10、带权图或网
1
2
3
5
6
8
74
10
7
9
6
6
7
12
315
16
A
B
D
C
E
60
30
45
35
80
40
75
?若给图中每一条边附加一个实数作为权，则该图称
为 带权图或网。
7.1 图的定义和术语
?这些权可以表示从一个顶点到另一个顶点的距离或
花费的代价。
10北京邮电大学自动化学院
?一、图的数组 (邻接矩阵 )存储表示
7.2 图的存储结构
?二、图的邻接表存储表示
?三、有向图的十字链表存储表示
?四、无向图的邻接多重表存储表示
11北京邮电大学自动化学院
? 用两个数组分别存储数据元素（顶点）的信息和数据元素
之间的关系（边或弧）的信息。
一、数组表示法（邻接矩阵 ）
??
??? ????
，其它0
E ( G )v,v或)v,(v若1,],[ jijijiA
? 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点
表，还有一个表示各个顶点之间关系的邻接矩阵。
? 设图 A = (V,E)是一个有 n 个顶点的图，则图的邻接矩阵
定义：
? 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不
对称的。
12北京邮电大学自动化学院
例
G1
2
4
1
3
例 1
5
3
2
4
G2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
???? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110?
?
?
?
????一、数组表示法（邻接矩阵）
13北京邮电大学自动化学院
? 借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相
连，并容易求得各个顶点的度。
??
?
??
1
0
)__(]][[)(
n
j
i NU MV E R T E XM A XnjiAVTD
? 对于无向量，顶点 Vi的度是邻接矩阵中第 i行（或第 i列） 的元
素之和，即
? 对于有向图,第 i行的元素之和为顶点 Vi的出度 OG（ Vi ），
第 j列的元素之和为顶点 Vj的入度 ID(Vj)。
一、数组表示法（邻接矩阵）
例
G1
2
4
1
3
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110?
?
?
?
????
14北京邮电大学自动化学院
?网的邻接矩阵可定义为：
?
?
?
?
????
，其它
E ( G )v,v或)v,(v若,],[ jijiijwjiA
例 1
4
5
2
3
7
5
3
1
8
6
4
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
6183
624
127
845
375
???? ?
?
?
?
?
?
一、数组表示法（邻接矩阵）
15北京邮电大学自动化学院
二、图的邻接表存储表示
? 邻接表 是图的一种链式存储结构。 在邻接表中，对
图中每个顶点建立一个单链表,第 i个单链表中的
结点表示依附于顶点 Vi的边（对有向图中指以顶点
Vi为尾的弧）。
adjvex nextarc info? 每个结点有三个域组成：
? 邻接结点域 (adjvex)：指示与顶点 Vi邻接的点在图
中的位置。
? 链域 (nextarc)：指示下一条边或弧的结点。
? 数据域 (info)：存储和边相关的信息，如权值等
16北京邮电大学自动化学院
? 每个链表上附设一个表头结点。在表头结点中，除了设有链域
(firstarc)指向链表中第一个结点之外，还设有存储顶点 Vi的名
或其它有关信息的数据域 (data)。
头结点 data firstarc
二、图的邻接表存储表示
例 V1
V5
V3
V2
V4
G2
0
1
2
3
V1
V3
V4
V2
vexdatafirstarc
1
4
2
3 ^
^
^
adjvexnext
4 V5
2
2 0 ^4
1
0
2 1 ^
17北京邮电大学自动化学院
? 若无向图中有 n个顶点,e条边，则它的邻接表需 n个头结点
和 2e个表结点。 显然，在边稀疏 (e<<n(n-1)/2)的情况下，用
邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息
较多时更是如此。
二、图的邻接表存储表示
例 V1
V5
V3
V2
V4
G2
0
1
2
3
V1
V3
V4
V2
vexdatafirstarc
1
4
2
3 ^
^
^
adjvexnext
4 V5
2
2 0 ^4
1
0
2 1 ^
18北京邮电大学自动化学院
例
G1
V2
V4
V1
V3
0
1
2
3
V1
V3
V4
V2
vexdatafirstarc
2 1
3
0
^
^
^
^
adjvexnext
二、图的邻接表存储表示
? 在无向图的邻接表中，顶点 vi的度恰为第 i个链表中的结点数；
? 而在有向图中，第 i个链表中的结点个数只是顶点 vi的出度，为
求入度，必须遍历整个邻接表。
? 在所有链表中其邻接点域的值为 i的结点的个数是顶点 vi的入
度。
19北京邮电大学自动化学院
A
B E
C D
二、图的邻接表存储表示
? 有时，为了便于确定顶点的入度或以顶点 vi为头的弧，可以建
立一个有向图的逆邻接表，即对每个顶点 vi 建立一个链接以 vi
为头的弧的链表。
? 在邻接表上容易找到任一顶点的第 1个邻接点和下一个邻接点，
3 ?
3 0 ?
4 ?
2 ?
0 ?E
D
C
B
A
4
3
2
1
0
? 但是要判定任意两个顶点（ vi和 vj）之间是否有边或狐相连，则
需搜索第 i个或第 j个链表，因此，不及邻接矩阵方便。
20北京邮电大学自动化学院
三、有向图的十字链表表示法
? 十字链表 是有向图的另一种链式存储结构。可以看成是将
有向图的邻接表和逆邻接表结合起来得到的一种链表。
? 在十字链表中，对应于有向图中每一条弧有一个结点，对
应于每一个顶点也有一个结点。这些结点的结构如下：
弧的结点结构
弧尾顶点位置 弧头顶点位置 弧的相关信息
指向下一个
有相同弧尾
的结点
指向下一个有
相同弧头的结
点
tailvex headvex hlink tlink info
21北京邮电大学自动化学院
顶点信息数据
指向该顶点的
第一条入弧
指向该顶点的
第一条出弧
data firstin firstout
顶点结点
三、有向图的十字链表表示法
? 在十字链表中，既容易找到以 vi为尾的狐，也容易找到以 vi尾
头的狐，因而容易求得顶点的出度和入度。
? 建立十字链表的时间复杂度和建立邻接表是相同的。在某些
有向图中，十字链表是很有用的工具。
22北京邮电大学自动化学院
例 V2
V4
V1
V3
V1
V2
V3
V4
0
1
2
3
0 20 1
2 32 0
3 23 13 0
^
^
^
^^ ^ ^
^
三、有向图的十字链表表示法
23北京邮电大学自动化学院
四、无向图的邻接多重表存储表示
? 邻接多重表是无向图的另一种链式存储结构。邻接多重表的结
构和十字链表类似。在邻接多重表中，每一条边用一个结点表
示，它由如下所示的六个域组成：
mark ivex ilink jvex jlink info
? mark为标志域，可以用以标记该条边是否被搜索过。
? ivex和 jvex为该边依附的两个顶点在图中的位置。
? ilink指向下一条依附于顶点 ivex的边。
? jlink指向下一条依附于顶点 jvex的边。
? info为指向和边相关的各种信息的指针域。
24北京邮电大学自动化学院
例 v1
v5
v3
v2
v4
0
1
2
3
v1
v3
v4
v2
4 v5
0 1 0 3
2 32 1
2 4 4 1
^
^
^
^^
? 每一个顶点也用一个结点表示，它由如下所示的两个域组成：
data firstedge
? data域存储和该顶点相关的信息
四、无向图的邻接多重表存储表示
? firstedge域指示第一条依附于该顶点的边
25北京邮电大学自动化学院
7.3 图的遍历
? 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点
仅被访问一次。这一过程就叫做 图的遍历 。
? 通常有两条遍历图的路径：
?深度优先搜索遍历
?广度优先搜索遍历
26北京邮电大学自动化学院
1、深度优先搜索遍历 (DFS)方法
? 深度优先搜索遍历 类似于树的先根遍历，是树的先根
遍历的推广。
? 深度优先可以从图中某个顶点 V出发，访问此顶点，
? 若此时图中尚有顶点未被访问，则另选图中一个未曾
被访问的顶点作起点，重复上述过程，直至图中所有
顶点都被访问为止。
? 然后依次从 V的未被访问的邻接点出发，深度优先遍
历图，直至图中所有和 V有路径 的顶点都被访问到；
27北京邮电大学自动化学院
? （ 1）假定从图中的某一顶点 V出发进行遍历，首先访问
顶点 V，再访问一个与 V相邻的顶点 W，接着访问一个与
W相邻且未被访问的顶点。依次类推，直至某个被访问
的顶点的所有相邻顶点均被访问过为止。
? （ 2）然后退回到尚有相邻顶点未被访问的顶点 R，再从
顶点 R的一个未被访问的相邻顶点出发，重复上述过
程，直到图中所有和 V有路径相通的顶点都被访问过。
? （ 3）若此时 图中尚有顶点未被访问，则另选图中一个未
被访问的顶点作起点，重复上述过程，直至图中所有顶
点都被访问为止。
1、深度优先搜索遍历 (DFS)方法
28北京邮电大学自动化学院
深度遍历,V1? V2 ?V4 ?V8 ?V5 ?V3 ?V6 ?V7
1、深度优先搜索遍历 (DFS)方法
V1
V2
V4 V5
V3
V7V6
V8
例
1
2
3
4
1
3
4
2
vexdatafirstarc
2
7
8
3 ^
^
^
adjvexnext
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
29北京邮电大学自动化学院
V1
V2
V4 V5
V3
V7V6
V8
例 1
2
3
4
1
3
4
2
vexdatafirstarc
2
7
8
3 ^
^
^
adjvexnext
5 5
6
^4
8 2 ^
6
7
8
6
7
8
7 ^
^
^
深度遍历,V1?V2 ?V4 ?V8 ?V5 ?V3? V6 ?V7
1、深度优先搜索遍历 (DFS)方法
30北京邮电大学自动化学院
2、广度优先搜索遍历 (BFS)
? 方法,广度优先遍历类似于树的按层次遍历的过程 。假设
从图中某顶点 V出发，访问此顶点 V后，依次访问 V的各个
未曾访问过的邻接点；
? 若此时图中尚有顶点未被访问，则另选图中一个未被访
问的顶点作起点，重复上述过程，直至图中所有顶点都
被访问为止。
? 然后分别从这些邻接点出发依次访问它们的邻接点，并使
“先被访问的顶点的邻接点”先于“后被访问的顶点的邻
接点” 被访问，直至图中所有已被访问的顶点的邻接点都
被访问到；
31北京邮电大学自动化学院
V1
V2
V4 V5
V3
V7V6
V8
例
? 广度遍历
V1
V2
V4 V5
V3
V7V6
V8
例
V1?
V2 ?V1? V3 ? V4 ? V5 ? V6 ? V7 ? V8
? 广度遍历
V2 ? V3 ? V4 ? V6 ? V7 ? V8 ? V5
2、广度优先搜索遍历 (BFS)
32北京邮电大学自动化学院
7.4 最小生成树
? 假设要在 n个城市间建立通信联络网，则连通 n个城市只需 n-1条
线路。这时，自然会考虑这样一个问题，如何在最节省经费的
前提下建立这个通讯网？
? 在每个城市之间都可以设置一条线路，相应地都要付出一定的
经济代价。 n个城市之间，最多可能设置 n(n-1)/2条线路，那
么，如何在这些可能的线路中选择 n-1条，以使总的耗费最少
呢？
? 可以用连通网来表示 n个城市以及 n个城市间可能设置的通讯线
路，其中 网的 顶点表示城市，边表示两个城市之间的线路，赋
于边的权值表示相应的代价 。对于 n个顶点的连通网可以建立许
多不同的生成树，每一棵生成树都可以是一个通讯网。
33北京邮电大学自动化学院
? 现在，我们要选择这样一棵生成树，也就是使总的耗费最
少，这个问题就是构造连通网的 最小代价生成树 （简称为最
小生成树）的问题。
? 一棵生成树的代价就是树上各边的代价之和。
? 构造最小生成树可以有多种方法。其中多数算法利用了最小生
成树的下列一种简称为 MST的性质,假设 N=（ V,{E}）是一个
连通网,U是顶点集 V的一个非空子集。若（ u,v）是一条具有
最小权值（代价）的边，其中 u?U,v?V-U，则必存在一棵包
含边（ u,v）的最小生成树。
? 普里姆 算法 和克鲁斯卡尔 算法 是两个利用 MST性质构造最小生
成树的算法。
7.4 最小生成树
34北京邮电大学自动化学院
1、普里姆 算法
? 假设 N=（ V,{E})是连通图,TE是 N上最小生成树中边的集合,
算法从 U={u0}(u0 ? V),TE={}开始，重复执行下述操作,
? 在所有 u∈ U,v∈ V－ U的边 (u,v) ?E中,找一条代价最小的边
（ u0,v0）并入集合 TE，同时 v0并入 U中，
? 如此不断重复,直到 U＝ V为止。此时 TE必有 n-1条边,则 T
（ V,{TE}）为 N的最小生成树。
35北京邮电大学自动化学院
? 如此进行下去，每次往生成树 里加一个顶点和一条权值最小
的边,直到把所有的顶点都包括进生成树。
1、普里姆 算法
? 从任意一个顶点开始,首先把这个顶点包括在生成树里，
? 然后在那些其一个端点已在生成树里另一个端点还未在生成
数里的边中,找权值最小的一条边,
? 当有两条具有同样的最小权值的边可供选择时，选哪一条都
行。
? 并把这条 边和其不在生成树里的那个端点包括进生成树里 。
36北京邮电大学自动化学院
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4 2
1
1
6
4
3
2 1
4 2
5
1
65
4
3
2 1
4 2
5
3
1、普里姆 算法
37北京邮电大学自动化学院
? 为了实现这个算法需附设一个辅助数组 closedge,以记录从 U到 V-
U具有最小代价的边,对每个顶点 vi ? V-U，在辅助数组中存在一
个相应分量 closedge[i-1]，它包含两个域，其中 lowcost存储该
边上的权。显然,Closedge[i-1].lowcost=Min{cost(u,vi) |u
?U},vex域存储该边依附的在 U中的顶点。
? 初始状态时,由于 U={v1},则到 V-U中各顶点的最小边,即为从依附
于顶点 1的各条边中,找到一条代价最小的边（ u0,v0） =（ 1,3）
为生成树上的第一条边,同时将 v0（ = v3）并入集合 U.
? 然后修改辅助数组中的值。首先将 closedge [2],Lowcost 改为
,0”,以示顶点 v3以并入 U。然后,由于边（ v3,v2）上的权值小
于 closedge[1].lowcost,则需修改 closedge[1].lowcost为边
（ v3,v2）及其权值。同理修改 closedge[4]和 closedge[5]。
依次类推，直至 U=V。
1、普里姆 算法
38北京邮电大学自动化学院
closedge i 1 2 3 4 5 U V-U k
Adjvex
lowcost
v1
6
v1
1
v1
5
{v1} {v2,v3,v4,v5,v6} 2
? 构造最小生成树过程中辅助数组中各分量的值
Adjvex
lowcost
v3
5
0 v1
5
v3
6
v3
4
{v1,v3} {v2,v4,v5,v6} 5
Adjvex
lowcost
v3
5
0 v6
2
v3
6
0 {v1,v3,v6} {v2,v4,v5} 3
Adjvex
lowcost
v3
5
0 0 v3
6
0 {v1,v3,v6,v4} {v2,v5} 1
Adjvex
lowcost
0 0 0 v2
2
0 {v1,v3,v6,v4,v2} {v5} 4
Adjvex
lowcost
0 0 0 0 0 {v1,v3,v6,v4,v2,v5} {}
1
65
4
3
2
6 51
3
5
6
6
4 2
5
39北京邮电大学自动化学院
? 设含 n个顶点的网中，边的权值全是正数。图用邻接矩阵表
示，若（ Vi,Vj）是边，则 A[i,j]的值等于此边上的权；若
（ Vi,Vj）不是边，则 A[i,j]的值是一个比任何边的权值都
大的正数 Max，矩阵的对角线元素全为 0。
? 构造最小生成树的过程,若顶点 Vi已包括进生成树里，就把
邻接矩阵对角线元素 A[i,j] 置为 1；无向图的邻接矩阵是对
称的，边（ Vi,Vj）对应两个矩阵元素 A[i,j]和 A[j, i ]，若
边（ Vi,Vj）已包括进生成树，就把矩阵元素 A[i,j]和 A[j，
i]两者中位于矩阵下三角中的一个置为负值。
1、普里姆 算法
? 算法结束时，邻接矩阵下三角部分为负的元素表示最小生成
树的边。在算法中用数组存放邻接矩阵 A，数组元素的下标
等于相关联的顶点序号减 1。
40北京邮电大学自动化学院
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
??
0624
6063
2055
465051
3506
5160
0 1 2 3 4 5
0
1
2
3
4
5
1
-2
1
-4
1
-1
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
-5
1-3
1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
4 2
5
3
1
1、普里姆 算法
41北京邮电大学自动化学院
? 普里姆算法 的时间复杂度为 O（ n2），与网中的边数
无关，因此 适用于求边稠密的网的最小生成树 。
2、克鲁斯卡尔 (Kruskal)算法
? 而 克鲁斯尔算法 恰恰相反，它的时间复杂度为
O(eloge)（ e为网中边的数目），因此，它相当于普里
姆算法而言,适合于求边稀疏的网的最小生成树 。
42北京邮电大学自动化学院
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
? 克鲁斯卡尔 (Kruskal)算法, 假设连通网 N=（ V,{E}），则令
最小生成树的初始状态为只有 n个顶点而无边的非连通图 T=
（ V,{}），图中每个顶点自成一个连同分量。在 E中选择代
价最小的边，若该边依附的顶点落在 T中不同的连通分量上，
则将此边加入到 T中，否则舍去此边而选择下一条代价最小的
边。依次类推，直至 T中所有顶点都在同一连通量上为止。
2、克鲁斯卡尔 (Kruskal)算法
43北京邮电大学自动化学院
? （ 1）用顶点数组和边数组存放顶点和边信息
? 顶点结点：
? typedef struct
? { int data; //顶点信息
? int jihe; }VEX;
? 边结点：
? typedef struct
? { int vexh,vext; //边依附的两顶点
? int weight; //边的权值
? int flag; //标志域 }EDGE;
? （ 2）初始时，令每个顶点的 jihe互不相同；每个边的 flag为 0
? （ 3）选出权值最小且 flag为 0的边
? （ 4）若该边依附的两个顶点的 jihe 值不同，即非连通，则令该
边的 flag=1,选中该边；
? （ 5）重复上述步骤，直到选出 n-1条边为止
? 再令该边依附的两顶点的 jihe以及两集合中所有顶点的 jihe相同。
? 若该边依附的两个顶点的 jihe 值相同，即连通，则令该边的
flag=2,即舍去该边
44北京邮电大学自动化学院
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
data jihe
1
2
4
5
3
6
1
2
4
5
3
6
1
2
4
5
3
6
vexh weight
1
1
2
2
1
3
2
3
3
5
4
4
vext flag
6
1
5
3
5
5
0
0
0
0
0
0
0
1
3
4
2
5
6
7
8
9
3
3
4
5
5
6
6
6
6
4
2
6
0
0
0
0
1
1
1
1
1
4
2
1
1
1
2
2
2
2
21
65
4
3
2 1
23 4
5
2、克鲁斯卡尔 (Kruskal)算法
45北京邮电大学自动化学院
? 例如，一个软件专业的学生必须学习一系列基本课程，其
中有些课是基础课，它独立于其它课程，如, 高等数
学, ；而另一些课程必须在学完作为它的基础的先修课程
才能开始。如在, 程序设计基础, 和, 离散数学, 学完之
前就不能开始学习, 数据结构, 。
7.5 拓扑排序
? 这些先决条件定义了课程之间的优先关系。这个关系可以
用有向图更加清楚地表示，图中顶点表示课程，有向弧表
示先决条件。若课程 i是课程 j的先决条件，则图中有弧
<i,j>。
? 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地
完成学业 —— 拓扑排序
46北京邮电大学自动化学院
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
7.5 拓扑排序
课程编号 课程名称 先决条件
C1 程序设计 无
C2 离散数学 C1
C3 数据结构 C1,C2
C4 汇编语言 C1
C5 语言的设计和分析 C3,C4
C6 计算机原理 C11
C7 编译原理 C5,C3
C8 操作系统 C3,C6
C9 高等数学 无
C10 线性代数 C9
C11 普通物理 C9
C12 数值分析 C9,C10,C1
47北京邮电大学自动化学院
? AOV网 —— 这种用顶点表示活动，用弧表示活动间优先关
系的有向图称为顶点表示活动的网 (Activity On Vertex
network),简称 AOV网 。
? 在网中，若从顶点 i到顶点 j有一条有向路径，则 i是 j的前
驱,j是 i的后继。 若 <vi,vj>是图中有向边，则 vi是 vj的直接
前驱； vj是 vi的直接后继。
? AOV网中不允许有回路，这意味着某项活动以自己为先决
条件。
? 对于给定的 AOV网应首先判定网中是否存在环。检测的办
法是对有向图构造其顶点的拓扑有序序列，若网中所有顶
点都在它的拓扑有序序列中，则该 AOV网必定不存在环。
7.5 拓扑排序
48北京邮电大学自动化学院
? 在有向图中选一个没有前驱的顶点且输出之。
1、如何 拓扑排序？
? 拓扑排序 —— 把 AOV网络中各顶点按照它们相互之间的
优先关系排列成一个线性序列的过程叫拓扑排序。
如何 拓扑排序？
? 从图中删除该顶点和所有以它为尾的弧。
? 重复上述两步，直至全部顶点均已输出，或者当前图中
不存在无前驱的顶点为止。
49北京邮电大学自动化学院
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
? 拓扑序列,C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
? 或, C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个 AOV网的拓扑序列不是唯一的
1、如何 拓扑排序？
50北京邮电大学自动化学院
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
1、如何 拓扑排序？
51北京邮电大学自动化学院
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1
（ 1）
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2
（ 2）
1、如何 拓扑排序？
52北京邮电大学自动化学院
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3
（ 3）
C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4
（ 4）
1、如何 拓扑排序？
53北京邮电大学自动化学院
C6
C8
C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
C6
C8
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10 （ 8）
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5
（ 5）
C6
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7
（ 6）
1、如何 拓扑排序？
54北京邮电大学自动化学院
C6
C8
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11
（ 9）
C8
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6
（ 10）
C8
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6--C12
（ 11） 拓扑序列,C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
（ 12）
1、如何 拓扑排序？
55北京邮电大学自动化学院
? 如何在计算机中实现？
2、排序算法的实现
? 针对上述两步操作，我们可采用邻接表作有向图的存储结构，
且在头结点中增加一个存放顶点入度的数组（ indegree）。入
度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧
的操作，则可换以弧头顶点的入度减 1来实现。
? 为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度
为零的顶点。
? 为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同
时设置一个栈来存储所有入度为 0 的顶点。
? 在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为 0
的顶点都推入栈中，一旦排序过程中出现新的入度为 0 的顶点，
也同样将其推入栈中。
56北京邮电大学自动化学院
? 邻接表结点：
? typedef struct node
? { int vex; //顶点域
? struct node *next; //
链域 }JD;
? 表头结点：
? typedef struct tnode
? { int in; //入度域
? struct node *link; //链域
? }TD;TD g[M]; //g[0]不用
? 算法实现（以邻接表作存储结构）
? 把邻接表中所有入度为 0的顶点进栈
? 栈非空时，输出栈顶元素 Vj并退栈，在邻接表中查找 Vj的直接
后继 Vk,把 Vk的入度减 1；若 Vk的入度为 0则进栈 。
? 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是 n，
则有向图有环；否则，拓扑排序完毕 。
57北京邮电大学自动化学院
3
2
1
0
4
例
1 2
34
56
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
Ch6_40.c
top 16
top
top
3、算法描述
58北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
6top
top
3、算法描述
59北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
60北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
61北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
62北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
63北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p=NULL
3、算法描述
64北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
1
top
top
3、算法描述
65北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
top
p
3、算法描述
66北京邮电大学自动化学院
0
1
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
top
p
4
3、算法描述
67北京邮电大学自动化学院
0
1
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3、算法描述
68北京邮电大学自动化学院
0
1
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3、算法描述
69北京邮电大学自动化学院
0
0
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top 3
3、算法描述
70北京邮电大学自动化学院
0
0
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3
3、算法描述
71北京邮电大学自动化学院
0
0
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3
3、算法描述
72北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3
3、算法描述
73北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p=NULL
4
top
3
3、算法描述
74北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top 3
3、算法描述
75北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
3、算法描述
76北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
3、算法描述
77北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
3、算法描述
78北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
2
3、算法描述
79北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
2
3、算法描述
80北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
2
p=NULL
3、算法描述
81北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2
3
2
1
0
4
4
top 2
p=NULL
3、算法描述
82北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2
3
2
1
0
4
4
top
p=NULL
3、算法描述
83北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
4top
3、算法描述
84北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
top
p
3、算法描述
85北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
top
p
5
3、算法描述
86北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
top
p=NULL
5
3、算法描述
87北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4 5
3
2
1
0
4
top 5
3、算法描述
88北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4 5
3
2
1
0
4
top
p=NU
LL
3、算法描述
89北京邮电大学自动化学院
? 与 AOV-网相对应的是 AOE-网 (Activity On Edge)即边表示
活动的网。 AOE-网是一个带权的有向无环图，其中顶点表
示事件，弧表示活动，权表示活动持续的时间 。通常 AOE-
网可用来估算工程的完成时间。例如 一个工程有 11项活动，
9个事件。事件 V1—— 表示整个工程开始；事件 V9—— 表示
整个工程结束。
9
8
7
64
5
3
2
1
a6=2
7.6 关键路径
90北京邮电大学自动化学院
? 由于整个工程只有一个开始点和一个完成点，故在正常的情况
下，网中只有一个入度为零的点（称作源点）和一个出度为零
的点（叫做汇点）。
? 对 AOE-网有待研究的问题是：
? （ 1）完成整项工程至少需要多少时间？
? （ 2）哪些活动是影响工程进度的关键？
? 由于在 AOE-网中有些活动可以并行地进行，所以完成工程
的最短时间是从开始点到完成点的最长路径的长度（这里所
说的路径长度是指路径上各活动持续时间之和，不是路径上
弧的数目）。
? 路径长度最长的路径叫做关键路径 。
7.6 关键路径
91北京邮电大学自动化学院
? Ve(j)—— 表示事件 Vj的最早发生时间
? 活动的最迟开始时间 l(i)，这是在不推迟整个工程完成的前提
下，活动 ai最迟必须开始进行的时间。两者之差 l(i)-e(i)意味
着完成活动 ai的时间余量。
? 假设开始点是 v1，从 v1到 vi的最长路径长度叫做事件 vi的最早
发生时间。这个时间决定了所有以 vi为尾的弧所表示的活动
的最早开始时间。
? Vl(j)—— 表示事件 Vj的最迟发生时间
? e(i)—— 表示活动 ai的最早开始时间
? l(i)—— 表示活动 ai的最迟开始时间 l(i)
7.6 关键路径
j k
ai
92北京邮电大学自动化学院
? 例如，从 v1到 v9的最长路
径（ v1,v2,v5,v8，
v9），路径长度是 18，即
v9的最早发生时间是 18。
9
8
7
64
5
3
2
1
a6=2
? 而活动 a6的最早开始时间是 5，最迟开始时间是 8，如果 a6推
迟 3天开始或者延迟 3天完成，都不会影响整个工程的完成。
因此，分析关键路径的目的是辨别哪些是关键活动，以便争
取提高关键活动的工效，缩短整个工期。
7.6 关键路径
? 我们把 l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所
有活动都是关键活动，因此 提前完成非关键活动并不能加快
工程的进度 。
93北京邮电大学自动化学院
j k
ai
? (1)从 Ve(0)=0开始向前递推
11,,) },,()({)( ?????????? njTjijidutiVeM a xjVe i
? 其中,T是所有以第 j个顶点为头的弧的集合
20,,) },,()({)( ?????????? niSjijidu tjVlM i niVl j
? 由上分析可知，辨别关键活动就是要找 e(i)=l(i)的活动。为了
求得 AOE-网中活动的 e(i)和 l(i)，首先应求得事件的最早发生
时间 Ve(j)和最迟发生时间 Vl(j)。设活动 ai用弧 <j,k>表示，其
持续时间记为,dut(<j,k>),则有：
? 其中,S是所有以第 i个顶点为尾的弧的集合
? 如何求 ve(j)和 vl(j)？,需分两步进行
? (2)从 Vl(n)=Ve(n)开始向后递推
? e(i)=ve(j)
? l(i)=vl(k)-dut(<j,k>)
94北京邮电大学自动化学院
求关键路径步骤
? （ 1）输入 e条弧 <j,k>，建立 AOE-网的存储结构；
? （ 2）从源点 v0出发 ve[0]=0，按拓扑有序求其余各顶点的最
早发生时间 ve[i](1?i? n-1)。如果得到的拓扑有序序列中顶
点个数小于网中顶点数 n，则说明网中存在环，不能求关键
路径，算法终止，否则执行步骤（ 3）；
? （ 3）从汇点 vn出发，令 vl[n-1]=ve[n-1]，按逆序拓扑有序求
其余各顶点的最迟发生时间 vl[i]（ 0?i? n-2 ）；
? （ 4）根据各顶点的 ve和 vl值，求每条弧 s的最早开始时间
e(s)和最迟发生时间 l(s)。若某条弧满足条件 e(s)=l(s)，则为
关键活动。
95北京邮电大学自动化学院
? 算法实现
邻接表结点：
typedef struct node
{ int vex; //顶点域
int length;
struct node *next; //链域
}JD;
表头结点：
typedef struct tnode
{ int vexdata;
int in; //入度域
struct node *link; //链域
}TD;
TD g[M]; //g[0]不用
? 以邻接表作存储结构
? 从源点 v1出发，令 ve[1]=0,按拓扑序列求各顶点的 ve[i]
? 从汇点 vn出发，令 vl[n]=ve[n],按逆拓扑序列求其余各顶点的
vl[i]
? 根据各顶点的 ve和 vl值，计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的
关键活动
96北京邮电大学自动化学院
? 点和弧信息，建立其邻接表
9
8
7
64
5
3
2
1
a6=2
? 计算每个顶点的入度
? 对其进行拓扑排序
?排序过程中求顶点的 ve[i]
?将得到的拓扑序列进栈
?按逆拓扑序列求顶点的 vl[i]
?计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动
算法描述
97北京邮电大学自动化学院
9
8
7
64
5
3
2
1
a6=2
v1
v2
v3
v4
v5
v6
v7
v8
v9
顶点 ve vl
0
6
4
5
7
7
16
14
18
0
6
6
8
7
10
16
14
18
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
活动 e l l-e
?
?
?
?
?
?
0 0 0
0 2 2
6 6 0
4 6 2
5 8 3
7 7 0
7 7 0
7 10 3
16 16 0
14 14 0
0 3 3
e(i)=ve(j)
l(i)=vl(k)-dut(<j,k>)
求 ve(i)
求 vl(j)
求 e(i)
求 l(i)
求 l(i)-e(i)
98北京邮电大学自动化学院
? 加快 a8的速度,a8=5 ? a8=4，则
不能使整个工程由 16天缩减成 15
天完成，这是因为另一条关键路
径（ V1,V2,V5,V7,V9）不包
括关键活动 a8。
9
8
7
64
5
3
2
1
a6=2
? 关键活动 a1和 a4。如果 a1=6?a1=5，则整个工程可由 16天缩短
为 15天完成。
? 如果 a1=6?a1=4，整个工程却不能缩短为 14天完成，因为这时关
键路径变成（ V1,V4,V6,V8,V9），路径长度是 15天。
? 所以缩短关键活动的完成时间后,还需要重新计算 AOE-网的关键
路径,只有在不改变 AOE-网的关键路径的前提下,加快包含在所有
关键路径上的关键活动才可以缩短整个工程的完成时间。
99北京邮电大学自动化学院
7.7 最短路径
? 最短路径问题,如果从图中某一顶点 (称为源点 )到达另一
顶点 (称为终点 )的路径可能不止一条，如何找到一条路
径，使得沿此路径各边上的权值总和达到最小。
? 问题解法
?单源最短路径 — Dijkstra算法
?任意顶点对之间的最短路径 — Floyd算法
100北京邮电大学自动化学院
? 给定带权有向图 G和源点 v，求从 v到 G中其余各顶点的最短
路径。例如，下图所示带权有向图 G中从 V0到其余顶点之间
的最短路径。
无
<V0,V2>
<V0,V4,V3>
<V0,V4>
<V0,V4,V3,V5>
1、从某个源点到其余各顶点的最短路径
100 60
30
2010 10
5 50
V1
V2
V3
V4V0
V5 始点 终点 最短路径 长度
v0 v1
v2
v3
v4
v5
10
50
30
60
? 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径
中,各边上权值之和最小的一条路径 —— 最短路径。
101北京邮电大学自动化学院
迪杰斯特拉 (Dijkstra)算法思想
? 如何求得这些路径？
? 迪杰斯特拉提出了一个按路径长度递增的次序产生最短路
径的算法。
? 迪杰斯特拉算法思想,把图中所有顶点分成两组，第一组
包括已确定最短路径的顶点，第二组包括尚未确定最短路
径的顶点，按最短路径长度递增的顺序逐个把第二组的顶
点加到第一组中去，直至从 v0出发可以到达的所有顶点都
包括到第一组中。
? 在这过程中，总保持从 v0到第一组各顶点的最短路径长度
都不大于从 v0到第二组的任何顶点的最短路径长度。
102北京邮电大学自动化学院
求最短路径步骤
? 一开始第一组只包括顶点 v0，第二组包括其他所有的顶点，
v0对应的距离为 0。
? 第二组的顶点对应的距离是这样确定的：若图中有边 <v0，
vi>,vi的距离为此边所带的权值，否则 vi的距离为一个很大
的数（大于所有顶点间的路径长度）。
? 然后每次从第二组的顶点中选一个其距离值为最小的 vm加入
到第一组中。
? 每往第一组加入一个顶点 vm,就要对第二组中的各个顶点的
距离值进行一次修正。 若加进 Vm做中间顶点使从 v0到 vj的最
短路径比不加 vm的路径为短，则要修改 vj的距离值。 修改后
再选距离值最小的顶点加入到第一组中。
103北京邮电大学自动化学院
? 如何求得这些路径？首先，引进一个辅助向量 D，它的每
个分量 D[i]表示当前所找到的从始点 v到每个终点 vi的最短
路径的长度。它的初态为：若从 v到 vi有弧，则 D[i]为弧上
的权值；否则置 D[i]为 ?。显然，长度为
}][{][ VviDjD iiM i n ??
}][{][ SVviDjD iiM i n ???
? 的路径就是从 V出发的长度最短的一条最短路径。此路径
为（ v,vj）。
? 下一条长度次短的路径的长度必是
? 其中,D[i]或是弧上（ v,vi）的权值，或是 D[k]（ vk
?S）和弧（ vk,vi）上的权值之和。
求最短路径步骤
104北京邮电大学自动化学院
算 法
? （ 1）假设用带权的邻接矩阵 arcs来表示带权有向图,arcs[i][j]
表示弧 <vi.vj>上的权值,若 <vi,vj>不存在，则置 arcs[i][j]为 ?.S
为已找到从 v出发的最短路径的终点的集合，它的初始状态为空
集。那么，从 v出发到图上其余各顶点（终点） vi可能达到的最
短路径长度的初值为,D[j]=arcs[Locate Vex(G,V)][i] |vi?V}
? （ 2）选择 vj，使得 D[j]=Min{D[i] |Vi?V-S},vj就是当前
求得的一条从 v出发的最短路径的终点。令 S=S U{j}
? （ 3）修改从 v出发到集合 V-S上任一顶点 vk可达的最短路径长度,
如果 D[j]+arcs[j][k]<D[k],则修改 D[k]为 D[k]=D[j]+arcs[j][k].
? (4) 重复操作（ 2）、（ 3）共 n-1次。由此求得从 v到图上其余
各顶点的最短路径是依路径长度递增的序列。
105北京邮电大学自动化学院
? void Shortpath_DIJ(MGraph G,int v0,PathMatrit &P,ShortPathTable
&D) { //用 Dijkstra算法求有向网的 v0顶点到其余顶点 v的最短路径 P[v]及
其带权长度 D[v]。若 P[v][w]为 TRUE，则 w是从 v0到 v当前求得最短路径
上的顶点。 final[v]为 TRUE当且仅当 v?S，即已经求得从 v0到 v的最短路
径。
迪杰斯特拉算法
? for (v=0; v<G.vexnum;++v){
? final[v]=FALSE; D[v]=G.arcs[v0][v];
? for(w=0; w<G.vexnum;++w) P[v][w]=FALSE;//设空路径
? if (D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;} }//for
? D[v0=0;final[v0]=TRUE;//初始化,v0顶点属于 S集。
? //开始主循环，每次求得 v0到某个 v顶点的最短路径，并加 v到 S集
106北京邮电大学自动化学院
迪杰斯特拉算法
? for (i=1; i<G.vexnum; ++i) { //其余 G.vexnum-1各顶点
? min=INFINTY; //当前所知离 v0顶点的最近距离
? } //for }//ShortwstPath_DIJ
? for (w=0;w<G.vexnum;++w)
? If (!final[w]) //w顶点在 V-S中
? if(D[w]<min){v=w;min=D[w];} //w顶点离 v0顶点更近
? final[v]=TRUE; //离 v0顶点最近的 v加入
? ……
107北京邮电大学自动化学院
迪杰斯特拉算法
? for (i=1;i<G.vexnum;++i){ //其余 G.vexnum-1各顶点
? final[v]=TRUE; //离 v0顶点最近的 v加入 S
? for(w=0;w<G.vexnum;++w) //更新当前最短路径及距离
? }//if }//for }//ShortwstPath_DIJ
? If(!final[w]&&(min+G.arca[v][w]<D[w])){ //修改 D[w]和
P[w],w?V-S
? D[w]=min+G.arcs[v][w];
? P[w]=P[v];P[w][w]=TRUE; //P[w]=P[v]+P[w]
108北京邮电大学自动化学院
?
10
<v0,v2>
?
30
<v0,v4>
100
<v0,v5>
v2
{v0,v2}
?
-------
60
<v0,v2,v3>
30
<v0,v4>
100
<v0,v5>
v4
{v0,v2,v4}
?
-------
50
<v0,v4,v3>
-------
90
<v0,v4,v5>
v3
{v0,v2,v4,v3}
?
-------
-------
-------
60
<v0,v4,v3,v5>
v5
{v0,v2,v3,v4,v5}
?
无
--------
--------
--------
-------
终点 从 V0到各终点的最短路径及其长度
V1
V2
V3
V4
V5
Vj
S
100 60
30
2010 10
5 50
V1
V2
V3
V4V0
V5求最短路径步骤
109北京邮电大学自动化学院
? 人们可能希望找到从源点到某一特定点的终点的最短路径，
但是，这个问题和求解点到其他所有顶点的最短路径一样复
杂，其时间复杂度也是的 O(n2)。
110北京邮电大学自动化学院
2、每一对顶点之间的最短路径
解决办法：
? 方法二,弗洛伊德 (Floyd)算法
? 弗洛伊德算法 思想：逐个顶点试探
? 初始时设置一个 n阶方阵，令其对角线元素为 0，若
存在弧 <vi,vj>,则对应元素为权值；否则为 ?。
? 逐步试着在原直接路径中增加中间顶点，若加入中间
点后路径变短，则修改之；否则，维持原值 。
? 所有顶点试探完毕，算法结束。
? 方法一,每次以一个顶点为源点，重复执行 Dijkstra
算法 n次 —— T(n)=O(n3)
111北京邮电大学自动化学院
? 假设求从顶点 vi到 vj的最短路径。如果从 vi到 vj有弧，则从
vi到 vj存在一条长度为 arcs[i][j]的路径，该路径不一定是最
短路径，尚需进行 n次试探。
? 首先考虑路径（ vi,v0,vj）是否存在（即判别弧（（ vi，
v0），（ v0,vj）是否存在）。如果存在，则比较（ vi，
vj）和（ vi,v0,vj）的路径长度，取长度较短者为从 vi到 vj
的中间顶点的序号不大于 0的最短路径。
? 假设在路径上再增加一个顶点 v1，也就是说，如果（ vi,
?, v1 ）和（ v1,?, vj）分别是当前找到的中间顶点的
序号不大于 0的最短路径，那么（ vi,? v1,?, vj） 就有
可能是从 vi到 vj的中间顶点的序号不大于 1的最短路径。
2、每一对顶点之间的最短路径
112北京邮电大学自动化学院
? 将它和已经得到的从 vi到 vj中间顶点序号不大于 0的最短路
径相比较，从中选出中间顶点的序号不大于 1的最短路径
后，再增加一个顶点 v2，继续进行试探。
? 依此类推。在一般情况下，若（ vi,? vk）和（ vk,?,vj）
分别是从 vi到 vk和从 vk到 vj的中间顶点序号不大于 k-1的最短
路径,则将（ vi,? vk? vj）和已经得到的从 vi到 vj且中间
顶点序号不大于 k-1的最短路径相比较，其长度较短者便是
从 vi到 vj的中间顶点的序号不大于 k的最短路径。
? 这样经过 n次比较后，最后求得的必是从 vi到 vj的最短路
径。按此方法，可以同时求得各对顶点间的最短路径。
2、每一对顶点之间的最短路径
113北京邮电大学自动化学院
算法的基本思想
? 显然,A中记录了所有顶点对之间的最短路径长度。若要
求得到最短路径本身，还必须设置一个路径矩阵 P[n][n]，
在第 k次迭代中求得的 path[i][j]，是从 i到 j的中间点序号不
大于 k的最短路径上顶点 i的后继顶点 。算法结束时，由
path[i][j]的值就可以得到从 i到 j的最短路径上的各个顶
点。
]][[]][[0 jiCjiA ?
]}][[]][[],][[m i n {]][[1 jkAkiAjiAjiA kkkk ???
? 从初始的邻接矩阵 A0开始，递推地生成矩阵序列 A1，
A2,...,An
114北京邮电大学自动化学院
弗洛伊德算法
? void shortpath_FLOYD(int cost[][M],int path[][M],int length[][M],int
n){//用 Floyd算法求有向图 G中各队顶点 v和 w之间德最短路径 P[v][w]及
其带权长度 D[v][w]。若 P[v][w][u]为 TRUE，则 u是从 v到 w当前求得最
短路径上的顶点。
? For (v-0;v,G.vexnum;++w)//
? For (w=0;w<G.vexnum;++w){
? D[v][w]=G.arcs[v][w];
? For (u-0;u,G.vexnum;++u) P[v][w][u]=FALSE;
? IF (D[v][w]<INFINTY){//vw
? P[v][w]=TRUE;P[v][w][u]=TRUE
? }//if } //for
115北京邮电大学自动化学院
弗洛伊德算法
? for(u=0;u<G.vexnum;++u)
? for(v=0;v<G.vexnum;++v))
? for(w=0;w<G.vexnum;++w)
? if(D[v][u]+D[u][w]<D[v][w]) //vuw
? { D[v][w]=D[v][w]+D[u]wj];
? for (i=0;i<G.vexnum;++i)
? P[v][w][i]=P[v][u][i] || P[u][w][i];
? }// if
? }//ShortestPath_Floyd
116北京邮电大学自动化学院
A
C
B
2
6
4
3 11
算法的基本思想
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 1 1
2 0 2
3 1 0
path=
0 4 11
6 0 2
3 ? 0
初始,路径：
AB AC
BA BC
CA
0 1 1
2 0 2
3 0 0
path=
0 4 6
6 0 2
3 7 0
加入 V2,路径,AB ABCBA BC
CA CAB
0 1 2
2 0 2
3 1 0
path=
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
0 1 2
3 0 2
3 1 0
path=
1
3
2
2
6
4
3 11
117北京邮电大学自动化学院
?1,熟悉图的各种存储结构及其构造算法。
? 2,熟练掌握图的两种搜索路径的遍历：遍历的逻
辑定义、深度优先搜索和广度优先搜索的算法。
? 3、熟练掌握最小生成树的普里姆算法。
? 4、熟练掌握如何进行拓扑排序？
? 5、熟练掌握关键路径的计算。
? 6、熟练掌握求最短路径（从某个源点到其余各顶点
的最短路径）的基本思想。
第 7章复习提纲
118北京邮电大学自动化学院
第七章 作业
? 一、单项选择题
? 1、一个 n个顶点的无向图最多有 条边。
? （ A） n （ B） n(n-1) （ C） n(n-1)/2 （ D） 2n
? 2、在一个有向图中，所有顶点的入度之和等于所有顶点的
出度之和的 倍。
? （ A） 1/2 （ B） 1 （ C） 2 （ D） 4
? 3、关键路径是事件结点网络中 。
? （ A）从源点到汇点的最长路径 （ B）最长的回路
? （ C）从源点到汇点的最短路径 （ D）最短的回路
119北京邮电大学自动化学院
? 4、下面不正确的说法是 。
? A、关键活动不按期完成就会影响整个工程的完成时间
? B、任何一个关键活动提前完成，将使整个工程提前完成
? C、所有关键活动都提前，则整个工程提前完成
? D、某些关键活动若提前完成，将使整个工程提前完成。
第七章 作业
120北京邮电大学自动化学院
? 二、填空题
? 1、一个图的 表示法是惟一的，而 表示法
是不惟一的。
? 2、在有 n个顶点的有向图中，每个顶点的度最大可
达 。
第七章 作业
121北京邮电大学自动化学院
? 1、设有向图 G如下图所示，试给
出：
? （ 1）该图的邻接矩阵；
? （ 2）该图的邻接表；
? （ 3）从 V1出发的“深度优先”遍历
序列；
? （ 4）从 V1出发的“广度优先”遍历
序列。
V1
V2
V4 V5
V3
V7V6
V8
第七章 作业
122北京邮电大学自动化学院
? 2、对下图的 AOE网，求出：
? （ 1）每个事件的最早发生时间和最迟发生时间；
? （ 2）每个活动的最早开始时间和最迟开始时间；
? （ 3）画出关键活动组成的图。对哪些活动提速，可使整个
工期提前。
第 7章作业
9
8
7
64
5
3
2
1
a6=2
123北京邮电大学自动化学院
第 7章 上机实习题
? 1、校园导游咨询
? 【 问题描述 】, 设计一个校园导游程序，为来访的客人提
供各种信息查询服务。
? 【 基本要求 】,
? （ 1）设计北邮校园平面图，所含景点不少于 10个。以图
中顶点表示校内各景点，以边表示路径，存放路径长度等
相关信息；
? （ 2）为来访客人提供图中任意景点间的问路查询，即查
询任意两个景点之间的一条最短的简单路径。
? 【 实现提示 】, 一般情况下，校园的道路是双向通行的，
可设校园平面是一无向网。顶点和边均含有相关信息。
124北京邮电大学自动化学院
第七章 上机时间及地点
班 级 时 间 地 点 老 师
0215301～ 302 12.10日 (周五）
14:00~17:00
4－ 328
4－ 328
张志霞
李维成
03501~502 12.11日 (周六）
14:00~17:00
4－ 327
4－ 328
杜 伟
王松月
03503～ 04 12.11日 (周六）
16:00~19:00
4－ 328
4－ 328
王松月
杜 伟
03507~509 12.11(周六）
18:00~22:00
4－ 327
4－ 328
李维成
张志霞
第 7章 图
? 7.1 图的定义和术语
? 1、图、顶点、边
? 图 G是由集合 V(G)和 E(G)组成,记为 G=(V,E)，其中 V(G)是顶
点的非空有限集合,E(G)是边的有限集合，边是点的无序对
或有序对。
? 2,有向图、弧、无向图
2 4 5
1 3 6
G1
? 若图中的边是顶点的有序对，则称此图为 有向图。
? 有向边又称为 弧,通常用尖括号表示一条有向边,<v,w>表
示从顶点 v到 w顶点的一条弧,v称为边的始点（或 弧尾 ）,w
称 为边的终点（或 弧头 ）。
2北京邮电大学自动化学院
例
2 4 5
1 3 6
G1
? 图 G1中,V(G1)={1,2,3,4,5,6}
? E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}
例
1 5 7
3 2 4
G2
6
? 图 G2中,V(G2)={1,2,3,4,5,6,7}
? 无向图 若图中的边是顶点的无序对，则称此图为 无向图 。通
常用园括号表示 无向边 。 （ v,w） 或（ w,v),并且（ v,w)=(w,v)
7.1 图的定义和术语
? E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
3北京邮电大学自动化学院
? 3、有向完全图、无向完全图
? 4、相邻顶点、相关联弧或边
? 无向完全图, n个顶点的无向图最大边数是 n(n-1)/2，具有
n(n-1)/2条边的无向图称为无向完全图。
2
1 3
有向完全图
2
1 3
无向完全图
7.1 图的定义和术语
? 若 <V1,V2> ?E或 (V1,V2) ?E,则 V1,V2是 相邻顶点,弧
<V1,V2>或边 (V1,V2)是与顶点 V1和 V2相关联弧或边 。
? 有向完 全 图,具有 n(n-1)条弧的有向图称为有向完全图。
4北京邮电大学自动化学院
? 5、度
例 1
2 4 5
1 3 6
G1
? 顶点 2入度,1 出度,3
? 顶点 4入度,1 出度,0
例 2
1 5 7
3 2 4
G2
6
? 顶点 5的度,3
? 顶点 2的度,4
7.1 图的定义和术语
? 一个顶点 V的度是与该顶点相关联的边的数目，记为 TD（ V）。
? 对于有向图，则把以顶点 V为弧尾的数目称为点 V的出度，
记为 OD（ V），把以顶点 V为头的弧的数目称为顶点 V的入
度，记为 ID（ V）。 顶点 V的度为：
?TD（ V） =ID（ V） +OD（ V）
5北京邮电大学自动化学院
? 6、子图
? 设有两个图 G＝ (V,E) 和 G‘＝ (V’,E‘)。若 V’? V 且
E‘?E,则称 图 G’ 是 图 G 的子图。
7.1 图的定义和术语
6北京邮电大学自动化学院
? 7、路径
? 若一条路径上除了 vi 和 vj 可以相同外,其余顶点均不相同，则
称此路径为一条 简单路径 。
7.1 图的定义和术语
? 在无向图 G＝ (V,E) 中,若存在一个顶点序列 vp1,vp2,…,v pm，
使得 (vi,vp1),(vp1,vp2),...,(vpm,vj)均属于 E，则称顶点 vi到 vj
存在一 条路径。 路径长度定义为路径上边或弧的数目。
? 起点和终点相同的路径称为 简单回路或简单环 。
7北京邮电大学自动化学院
例 2
1 5 7
3 2 4
G2
6
例 1
2 4 5
1 3 6
G1
? 路径,1,2,3,5,6,3
? 路径,1,2,5,7,6,5,2,3
7.1 图的定义和术语
? 路径长度,5
? 简单路径,1,2,3,5
? 回路,1,2,3,5,6,3,1
? 简单回路,3,5,6,3
? 路径长度,7
? 简单路径,1,2,5,7,6
? 回路,1,2,5,7,6,5,2,1
? 简单回路,1,2,3,1
8北京邮电大学自动化学院
? 8、图的连通 在无向图 G中，若两个顶点 vi和 vj之间有路径存
在，则称 vi 和 vj 是连通的。 若 G中任意两个顶点都是连通的，
则称 G为连通图。
连通图
例
2 4 5
1 3 6
强连通图
3
5
6
例例 2 4 5
1 3 6
非连通图，连通分量
? 9、强连通图与强连通分量 在有向图中,若对于每一对顶点 vi
和 vj,都存在一条从 vi到 vj和从 vj到 vi的路径,则称此图是 强连通
图 。非强连通图的极大强连通子图叫做强连通分量。
7.1 图的定义和术语
? 非连通图的极大连通子图叫做 连通分量 。
9北京邮电大学自动化学院
?10、带权图或网
1
2
3
5
6
8
74
10
7
9
6
6
7
12
315
16
A
B
D
C
E
60
30
45
35
80
40
75
?若给图中每一条边附加一个实数作为权，则该图称
为 带权图或网。
7.1 图的定义和术语
?这些权可以表示从一个顶点到另一个顶点的距离或
花费的代价。
10北京邮电大学自动化学院
?一、图的数组 (邻接矩阵 )存储表示
7.2 图的存储结构
?二、图的邻接表存储表示
?三、有向图的十字链表存储表示
?四、无向图的邻接多重表存储表示
11北京邮电大学自动化学院
? 用两个数组分别存储数据元素（顶点）的信息和数据元素
之间的关系（边或弧）的信息。
一、数组表示法（邻接矩阵 ）
??
??? ????
，其它0
E ( G )v,v或)v,(v若1,],[ jijijiA
? 在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点
表，还有一个表示各个顶点之间关系的邻接矩阵。
? 设图 A = (V,E)是一个有 n 个顶点的图，则图的邻接矩阵
定义：
? 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不
对称的。
12北京邮电大学自动化学院
例
G1
2
4
1
3
例 1
5
3
2
4
G2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
00110
00101
11010
10101
01010
???? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110?
?
?
?
????一、数组表示法（邻接矩阵）
13北京邮电大学自动化学院
? 借助邻接矩阵容易判定任意两个顶点之间是否有边（或弧）相
连，并容易求得各个顶点的度。
??
?
??
1
0
)__(]][[)(
n
j
i NU MV E R T E XM A XnjiAVTD
? 对于无向量，顶点 Vi的度是邻接矩阵中第 i行（或第 i列） 的元
素之和，即
? 对于有向图,第 i行的元素之和为顶点 Vi的出度 OG（ Vi ），
第 j列的元素之和为顶点 Vj的入度 ID(Vj)。
一、数组表示法（邻接矩阵）
例
G1
2
4
1
3
?
?
?
?
?
?
?
?
?
?
?
?
?
?
0001
1000
0000
0110?
?
?
?
????
14北京邮电大学自动化学院
?网的邻接矩阵可定义为：
?
?
?
?
????
，其它
E ( G )v,v或)v,(v若,],[ jijiijwjiA
例 1
4
5
2
3
7
5
3
1
8
6
4
2
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
6183
624
127
845
375
???? ?
?
?
?
?
?
一、数组表示法（邻接矩阵）
15北京邮电大学自动化学院
二、图的邻接表存储表示
? 邻接表 是图的一种链式存储结构。 在邻接表中，对
图中每个顶点建立一个单链表,第 i个单链表中的
结点表示依附于顶点 Vi的边（对有向图中指以顶点
Vi为尾的弧）。
adjvex nextarc info? 每个结点有三个域组成：
? 邻接结点域 (adjvex)：指示与顶点 Vi邻接的点在图
中的位置。
? 链域 (nextarc)：指示下一条边或弧的结点。
? 数据域 (info)：存储和边相关的信息，如权值等
16北京邮电大学自动化学院
? 每个链表上附设一个表头结点。在表头结点中，除了设有链域
(firstarc)指向链表中第一个结点之外，还设有存储顶点 Vi的名
或其它有关信息的数据域 (data)。
头结点 data firstarc
二、图的邻接表存储表示
例 V1
V5
V3
V2
V4
G2
0
1
2
3
V1
V3
V4
V2
vexdatafirstarc
1
4
2
3 ^
^
^
adjvexnext
4 V5
2
2 0 ^4
1
0
2 1 ^
17北京邮电大学自动化学院
? 若无向图中有 n个顶点,e条边，则它的邻接表需 n个头结点
和 2e个表结点。 显然，在边稀疏 (e<<n(n-1)/2)的情况下，用
邻接表表示图比邻接矩阵节省存储空间，当和边相关的信息
较多时更是如此。
二、图的邻接表存储表示
例 V1
V5
V3
V2
V4
G2
0
1
2
3
V1
V3
V4
V2
vexdatafirstarc
1
4
2
3 ^
^
^
adjvexnext
4 V5
2
2 0 ^4
1
0
2 1 ^
18北京邮电大学自动化学院
例
G1
V2
V4
V1
V3
0
1
2
3
V1
V3
V4
V2
vexdatafirstarc
2 1
3
0
^
^
^
^
adjvexnext
二、图的邻接表存储表示
? 在无向图的邻接表中，顶点 vi的度恰为第 i个链表中的结点数；
? 而在有向图中，第 i个链表中的结点个数只是顶点 vi的出度，为
求入度，必须遍历整个邻接表。
? 在所有链表中其邻接点域的值为 i的结点的个数是顶点 vi的入
度。
19北京邮电大学自动化学院
A
B E
C D
二、图的邻接表存储表示
? 有时，为了便于确定顶点的入度或以顶点 vi为头的弧，可以建
立一个有向图的逆邻接表，即对每个顶点 vi 建立一个链接以 vi
为头的弧的链表。
? 在邻接表上容易找到任一顶点的第 1个邻接点和下一个邻接点，
3 ?
3 0 ?
4 ?
2 ?
0 ?E
D
C
B
A
4
3
2
1
0
? 但是要判定任意两个顶点（ vi和 vj）之间是否有边或狐相连，则
需搜索第 i个或第 j个链表，因此，不及邻接矩阵方便。
20北京邮电大学自动化学院
三、有向图的十字链表表示法
? 十字链表 是有向图的另一种链式存储结构。可以看成是将
有向图的邻接表和逆邻接表结合起来得到的一种链表。
? 在十字链表中，对应于有向图中每一条弧有一个结点，对
应于每一个顶点也有一个结点。这些结点的结构如下：
弧的结点结构
弧尾顶点位置 弧头顶点位置 弧的相关信息
指向下一个
有相同弧尾
的结点
指向下一个有
相同弧头的结
点
tailvex headvex hlink tlink info
21北京邮电大学自动化学院
顶点信息数据
指向该顶点的
第一条入弧
指向该顶点的
第一条出弧
data firstin firstout
顶点结点
三、有向图的十字链表表示法
? 在十字链表中，既容易找到以 vi为尾的狐，也容易找到以 vi尾
头的狐，因而容易求得顶点的出度和入度。
? 建立十字链表的时间复杂度和建立邻接表是相同的。在某些
有向图中，十字链表是很有用的工具。
22北京邮电大学自动化学院
例 V2
V4
V1
V3
V1
V2
V3
V4
0
1
2
3
0 20 1
2 32 0
3 23 13 0
^
^
^
^^ ^ ^
^
三、有向图的十字链表表示法
23北京邮电大学自动化学院
四、无向图的邻接多重表存储表示
? 邻接多重表是无向图的另一种链式存储结构。邻接多重表的结
构和十字链表类似。在邻接多重表中，每一条边用一个结点表
示，它由如下所示的六个域组成：
mark ivex ilink jvex jlink info
? mark为标志域，可以用以标记该条边是否被搜索过。
? ivex和 jvex为该边依附的两个顶点在图中的位置。
? ilink指向下一条依附于顶点 ivex的边。
? jlink指向下一条依附于顶点 jvex的边。
? info为指向和边相关的各种信息的指针域。
24北京邮电大学自动化学院
例 v1
v5
v3
v2
v4
0
1
2
3
v1
v3
v4
v2
4 v5
0 1 0 3
2 32 1
2 4 4 1
^
^
^
^^
? 每一个顶点也用一个结点表示，它由如下所示的两个域组成：
data firstedge
? data域存储和该顶点相关的信息
四、无向图的邻接多重表存储表示
? firstedge域指示第一条依附于该顶点的边
25北京邮电大学自动化学院
7.3 图的遍历
? 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点
仅被访问一次。这一过程就叫做 图的遍历 。
? 通常有两条遍历图的路径：
?深度优先搜索遍历
?广度优先搜索遍历
26北京邮电大学自动化学院
1、深度优先搜索遍历 (DFS)方法
? 深度优先搜索遍历 类似于树的先根遍历，是树的先根
遍历的推广。
? 深度优先可以从图中某个顶点 V出发，访问此顶点，
? 若此时图中尚有顶点未被访问，则另选图中一个未曾
被访问的顶点作起点，重复上述过程，直至图中所有
顶点都被访问为止。
? 然后依次从 V的未被访问的邻接点出发，深度优先遍
历图，直至图中所有和 V有路径 的顶点都被访问到；
27北京邮电大学自动化学院
? （ 1）假定从图中的某一顶点 V出发进行遍历，首先访问
顶点 V，再访问一个与 V相邻的顶点 W，接着访问一个与
W相邻且未被访问的顶点。依次类推，直至某个被访问
的顶点的所有相邻顶点均被访问过为止。
? （ 2）然后退回到尚有相邻顶点未被访问的顶点 R，再从
顶点 R的一个未被访问的相邻顶点出发，重复上述过
程，直到图中所有和 V有路径相通的顶点都被访问过。
? （ 3）若此时 图中尚有顶点未被访问，则另选图中一个未
被访问的顶点作起点，重复上述过程，直至图中所有顶
点都被访问为止。
1、深度优先搜索遍历 (DFS)方法
28北京邮电大学自动化学院
深度遍历,V1? V2 ?V4 ?V8 ?V5 ?V3 ?V6 ?V7
1、深度优先搜索遍历 (DFS)方法
V1
V2
V4 V5
V3
V7V6
V8
例
1
2
3
4
1
3
4
2
vexdatafirstarc
2
7
8
3 ^
^
^
adjvexnext
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
29北京邮电大学自动化学院
V1
V2
V4 V5
V3
V7V6
V8
例 1
2
3
4
1
3
4
2
vexdatafirstarc
2
7
8
3 ^
^
^
adjvexnext
5 5
6
^4
8 2 ^
6
7
8
6
7
8
7 ^
^
^
深度遍历,V1?V2 ?V4 ?V8 ?V5 ?V3? V6 ?V7
1、深度优先搜索遍历 (DFS)方法
30北京邮电大学自动化学院
2、广度优先搜索遍历 (BFS)
? 方法,广度优先遍历类似于树的按层次遍历的过程 。假设
从图中某顶点 V出发，访问此顶点 V后，依次访问 V的各个
未曾访问过的邻接点；
? 若此时图中尚有顶点未被访问，则另选图中一个未被访
问的顶点作起点，重复上述过程，直至图中所有顶点都
被访问为止。
? 然后分别从这些邻接点出发依次访问它们的邻接点，并使
“先被访问的顶点的邻接点”先于“后被访问的顶点的邻
接点” 被访问，直至图中所有已被访问的顶点的邻接点都
被访问到；
31北京邮电大学自动化学院
V1
V2
V4 V5
V3
V7V6
V8
例
? 广度遍历
V1
V2
V4 V5
V3
V7V6
V8
例
V1?
V2 ?V1? V3 ? V4 ? V5 ? V6 ? V7 ? V8
? 广度遍历
V2 ? V3 ? V4 ? V6 ? V7 ? V8 ? V5
2、广度优先搜索遍历 (BFS)
32北京邮电大学自动化学院
7.4 最小生成树
? 假设要在 n个城市间建立通信联络网，则连通 n个城市只需 n-1条
线路。这时，自然会考虑这样一个问题，如何在最节省经费的
前提下建立这个通讯网？
? 在每个城市之间都可以设置一条线路，相应地都要付出一定的
经济代价。 n个城市之间，最多可能设置 n(n-1)/2条线路，那
么，如何在这些可能的线路中选择 n-1条，以使总的耗费最少
呢？
? 可以用连通网来表示 n个城市以及 n个城市间可能设置的通讯线
路，其中 网的 顶点表示城市，边表示两个城市之间的线路，赋
于边的权值表示相应的代价 。对于 n个顶点的连通网可以建立许
多不同的生成树，每一棵生成树都可以是一个通讯网。
33北京邮电大学自动化学院
? 现在，我们要选择这样一棵生成树，也就是使总的耗费最
少，这个问题就是构造连通网的 最小代价生成树 （简称为最
小生成树）的问题。
? 一棵生成树的代价就是树上各边的代价之和。
? 构造最小生成树可以有多种方法。其中多数算法利用了最小生
成树的下列一种简称为 MST的性质,假设 N=（ V,{E}）是一个
连通网,U是顶点集 V的一个非空子集。若（ u,v）是一条具有
最小权值（代价）的边，其中 u?U,v?V-U，则必存在一棵包
含边（ u,v）的最小生成树。
? 普里姆 算法 和克鲁斯卡尔 算法 是两个利用 MST性质构造最小生
成树的算法。
7.4 最小生成树
34北京邮电大学自动化学院
1、普里姆 算法
? 假设 N=（ V,{E})是连通图,TE是 N上最小生成树中边的集合,
算法从 U={u0}(u0 ? V),TE={}开始，重复执行下述操作,
? 在所有 u∈ U,v∈ V－ U的边 (u,v) ?E中,找一条代价最小的边
（ u0,v0）并入集合 TE，同时 v0并入 U中，
? 如此不断重复,直到 U＝ V为止。此时 TE必有 n-1条边,则 T
（ V,{TE}）为 N的最小生成树。
35北京邮电大学自动化学院
? 如此进行下去，每次往生成树 里加一个顶点和一条权值最小
的边,直到把所有的顶点都包括进生成树。
1、普里姆 算法
? 从任意一个顶点开始,首先把这个顶点包括在生成树里，
? 然后在那些其一个端点已在生成树里另一个端点还未在生成
数里的边中,找权值最小的一条边,
? 当有两条具有同样的最小权值的边可供选择时，选哪一条都
行。
? 并把这条 边和其不在生成树里的那个端点包括进生成树里 。
36北京邮电大学自动化学院
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4 2
1
1
6
4
3
2 1
4 2
5
1
65
4
3
2 1
4 2
5
3
1、普里姆 算法
37北京邮电大学自动化学院
? 为了实现这个算法需附设一个辅助数组 closedge,以记录从 U到 V-
U具有最小代价的边,对每个顶点 vi ? V-U，在辅助数组中存在一
个相应分量 closedge[i-1]，它包含两个域，其中 lowcost存储该
边上的权。显然,Closedge[i-1].lowcost=Min{cost(u,vi) |u
?U},vex域存储该边依附的在 U中的顶点。
? 初始状态时,由于 U={v1},则到 V-U中各顶点的最小边,即为从依附
于顶点 1的各条边中,找到一条代价最小的边（ u0,v0） =（ 1,3）
为生成树上的第一条边,同时将 v0（ = v3）并入集合 U.
? 然后修改辅助数组中的值。首先将 closedge [2],Lowcost 改为
,0”,以示顶点 v3以并入 U。然后,由于边（ v3,v2）上的权值小
于 closedge[1].lowcost,则需修改 closedge[1].lowcost为边
（ v3,v2）及其权值。同理修改 closedge[4]和 closedge[5]。
依次类推，直至 U=V。
1、普里姆 算法
38北京邮电大学自动化学院
closedge i 1 2 3 4 5 U V-U k
Adjvex
lowcost
v1
6
v1
1
v1
5
{v1} {v2,v3,v4,v5,v6} 2
? 构造最小生成树过程中辅助数组中各分量的值
Adjvex
lowcost
v3
5
0 v1
5
v3
6
v3
4
{v1,v3} {v2,v4,v5,v6} 5
Adjvex
lowcost
v3
5
0 v6
2
v3
6
0 {v1,v3,v6} {v2,v4,v5} 3
Adjvex
lowcost
v3
5
0 0 v3
6
0 {v1,v3,v6,v4} {v2,v5} 1
Adjvex
lowcost
0 0 0 v2
2
0 {v1,v3,v6,v4,v2} {v5} 4
Adjvex
lowcost
0 0 0 0 0 {v1,v3,v6,v4,v2,v5} {}
1
65
4
3
2
6 51
3
5
6
6
4 2
5
39北京邮电大学自动化学院
? 设含 n个顶点的网中，边的权值全是正数。图用邻接矩阵表
示，若（ Vi,Vj）是边，则 A[i,j]的值等于此边上的权；若
（ Vi,Vj）不是边，则 A[i,j]的值是一个比任何边的权值都
大的正数 Max，矩阵的对角线元素全为 0。
? 构造最小生成树的过程,若顶点 Vi已包括进生成树里，就把
邻接矩阵对角线元素 A[i,j] 置为 1；无向图的邻接矩阵是对
称的，边（ Vi,Vj）对应两个矩阵元素 A[i,j]和 A[j, i ]，若
边（ Vi,Vj）已包括进生成树，就把矩阵元素 A[i,j]和 A[j，
i]两者中位于矩阵下三角中的一个置为负值。
1、普里姆 算法
? 算法结束时，邻接矩阵下三角部分为负的元素表示最小生成
树的边。在算法中用数组存放邻接矩阵 A，数组元素的下标
等于相关联的顶点序号减 1。
40北京邮电大学自动化学院
1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
??
??
??
??
??
0624
6063
2055
465051
3506
5160
0 1 2 3 4 5
0
1
2
3
4
5
1
-2
1
-4
1
-1
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
-5
1-3
1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
4 2
5
3
1
1、普里姆 算法
41北京邮电大学自动化学院
? 普里姆算法 的时间复杂度为 O（ n2），与网中的边数
无关，因此 适用于求边稠密的网的最小生成树 。
2、克鲁斯卡尔 (Kruskal)算法
? 而 克鲁斯尔算法 恰恰相反，它的时间复杂度为
O(eloge)（ e为网中边的数目），因此，它相当于普里
姆算法而言,适合于求边稀疏的网的最小生成树 。
42北京邮电大学自动化学院
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
? 克鲁斯卡尔 (Kruskal)算法, 假设连通网 N=（ V,{E}），则令
最小生成树的初始状态为只有 n个顶点而无边的非连通图 T=
（ V,{}），图中每个顶点自成一个连同分量。在 E中选择代
价最小的边，若该边依附的顶点落在 T中不同的连通分量上，
则将此边加入到 T中，否则舍去此边而选择下一条代价最小的
边。依次类推，直至 T中所有顶点都在同一连通量上为止。
2、克鲁斯卡尔 (Kruskal)算法
43北京邮电大学自动化学院
? （ 1）用顶点数组和边数组存放顶点和边信息
? 顶点结点：
? typedef struct
? { int data; //顶点信息
? int jihe; }VEX;
? 边结点：
? typedef struct
? { int vexh,vext; //边依附的两顶点
? int weight; //边的权值
? int flag; //标志域 }EDGE;
? （ 2）初始时，令每个顶点的 jihe互不相同；每个边的 flag为 0
? （ 3）选出权值最小且 flag为 0的边
? （ 4）若该边依附的两个顶点的 jihe 值不同，即非连通，则令该
边的 flag=1,选中该边；
? （ 5）重复上述步骤，直到选出 n-1条边为止
? 再令该边依附的两顶点的 jihe以及两集合中所有顶点的 jihe相同。
? 若该边依附的两个顶点的 jihe 值相同，即连通，则令该边的
flag=2,即舍去该边
44北京邮电大学自动化学院
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
data jihe
1
2
4
5
3
6
1
2
4
5
3
6
1
2
4
5
3
6
vexh weight
1
1
2
2
1
3
2
3
3
5
4
4
vext flag
6
1
5
3
5
5
0
0
0
0
0
0
0
1
3
4
2
5
6
7
8
9
3
3
4
5
5
6
6
6
6
4
2
6
0
0
0
0
1
1
1
1
1
4
2
1
1
1
2
2
2
2
21
65
4
3
2 1
23 4
5
2、克鲁斯卡尔 (Kruskal)算法
45北京邮电大学自动化学院
? 例如，一个软件专业的学生必须学习一系列基本课程，其
中有些课是基础课，它独立于其它课程，如, 高等数
学, ；而另一些课程必须在学完作为它的基础的先修课程
才能开始。如在, 程序设计基础, 和, 离散数学, 学完之
前就不能开始学习, 数据结构, 。
7.5 拓扑排序
? 这些先决条件定义了课程之间的优先关系。这个关系可以
用有向图更加清楚地表示，图中顶点表示课程，有向弧表
示先决条件。若课程 i是课程 j的先决条件，则图中有弧
<i,j>。
? 学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地
完成学业 —— 拓扑排序
46北京邮电大学自动化学院
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
7.5 拓扑排序
课程编号 课程名称 先决条件
C1 程序设计 无
C2 离散数学 C1
C3 数据结构 C1,C2
C4 汇编语言 C1
C5 语言的设计和分析 C3,C4
C6 计算机原理 C11
C7 编译原理 C5,C3
C8 操作系统 C3,C6
C9 高等数学 无
C10 线性代数 C9
C11 普通物理 C9
C12 数值分析 C9,C10,C1
47北京邮电大学自动化学院
? AOV网 —— 这种用顶点表示活动，用弧表示活动间优先关
系的有向图称为顶点表示活动的网 (Activity On Vertex
network),简称 AOV网 。
? 在网中，若从顶点 i到顶点 j有一条有向路径，则 i是 j的前
驱,j是 i的后继。 若 <vi,vj>是图中有向边，则 vi是 vj的直接
前驱； vj是 vi的直接后继。
? AOV网中不允许有回路，这意味着某项活动以自己为先决
条件。
? 对于给定的 AOV网应首先判定网中是否存在环。检测的办
法是对有向图构造其顶点的拓扑有序序列，若网中所有顶
点都在它的拓扑有序序列中，则该 AOV网必定不存在环。
7.5 拓扑排序
48北京邮电大学自动化学院
? 在有向图中选一个没有前驱的顶点且输出之。
1、如何 拓扑排序？
? 拓扑排序 —— 把 AOV网络中各顶点按照它们相互之间的
优先关系排列成一个线性序列的过程叫拓扑排序。
如何 拓扑排序？
? 从图中删除该顶点和所有以它为尾的弧。
? 重复上述两步，直至全部顶点均已输出，或者当前图中
不存在无前驱的顶点为止。
49北京邮电大学自动化学院
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
? 拓扑序列,C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
? 或, C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个 AOV网的拓扑序列不是唯一的
1、如何 拓扑排序？
50北京邮电大学自动化学院
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
1、如何 拓扑排序？
51北京邮电大学自动化学院
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1
（ 1）
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2
（ 2）
1、如何 拓扑排序？
52北京邮电大学自动化学院
C4 C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3
（ 3）
C5
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4
（ 4）
1、如何 拓扑排序？
53北京邮电大学自动化学院
C6
C8
C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
C6
C8
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10 （ 8）
C6
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5
（ 5）
C6
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7
（ 6）
1、如何 拓扑排序？
54北京邮电大学自动化学院
C6
C8
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11
（ 9）
C8
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6
（ 10）
C8
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6--C12
（ 11） 拓扑序列,C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8
（ 12）
1、如何 拓扑排序？
55北京邮电大学自动化学院
? 如何在计算机中实现？
2、排序算法的实现
? 针对上述两步操作，我们可采用邻接表作有向图的存储结构，
且在头结点中增加一个存放顶点入度的数组（ indegree）。入
度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧
的操作，则可换以弧头顶点的入度减 1来实现。
? 为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度
为零的顶点。
? 为了便于考察每个顶点的入度，在顶点表中增加一个入度域，同
时设置一个栈来存储所有入度为 0 的顶点。
? 在进行拓扑排序之前，只要对顶点表扫描一遍，将所有入度为 0
的顶点都推入栈中，一旦排序过程中出现新的入度为 0 的顶点，
也同样将其推入栈中。
56北京邮电大学自动化学院
? 邻接表结点：
? typedef struct node
? { int vex; //顶点域
? struct node *next; //
链域 }JD;
? 表头结点：
? typedef struct tnode
? { int in; //入度域
? struct node *link; //链域
? }TD;TD g[M]; //g[0]不用
? 算法实现（以邻接表作存储结构）
? 把邻接表中所有入度为 0的顶点进栈
? 栈非空时，输出栈顶元素 Vj并退栈，在邻接表中查找 Vj的直接
后继 Vk,把 Vk的入度减 1；若 Vk的入度为 0则进栈 。
? 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是 n，
则有向图有环；否则，拓扑排序完毕 。
57北京邮电大学自动化学院
3
2
1
0
4
例
1 2
34
56
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
Ch6_40.c
top 16
top
top
3、算法描述
58北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
6top
top
3、算法描述
59北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
3 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
60北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
61北京邮电大学自动化学院
0
1
2
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
62北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p
3、算法描述
63北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6
3
2
1
0
4
1
top
p=NULL
3、算法描述
64北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
1
top
top
3、算法描述
65北京邮电大学自动化学院
0
1
1
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
top
p
3、算法描述
66北京邮电大学自动化学院
0
1
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
top
p
4
3、算法描述
67北京邮电大学自动化学院
0
1
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3、算法描述
68北京邮电大学自动化学院
0
1
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3、算法描述
69北京邮电大学自动化学院
0
0
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top 3
3、算法描述
70北京邮电大学自动化学院
0
0
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3
3、算法描述
71北京邮电大学自动化学院
0
0
0
2
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3
3、算法描述
72北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p
4
top
3
3、算法描述
73北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1
3
2
1
0
4
p=NULL
4
top
3
3、算法描述
74北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top 3
3、算法描述
75北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
2 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
3、算法描述
76北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
3、算法描述
77北京邮电大学自动化学院
0
0
0
1
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
3、算法描述
78北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
2
3、算法描述
79北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
p
2
3、算法描述
80北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3
3
2
1
0
4
4
top
2
p=NULL
3、算法描述
81北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2
3
2
1
0
4
4
top 2
p=NULL
3、算法描述
82北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2
3
2
1
0
4
4
top
p=NULL
3、算法描述
83北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
4top
3、算法描述
84北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
1 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
top
p
3、算法描述
85北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
top
p
5
3、算法描述
86北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4
3
2
1
0
4
top
p=NULL
5
3、算法描述
87北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4 5
3
2
1
0
4
top 5
3、算法描述
88北京邮电大学自动化学院
0
0
0
0
in link
5
5
4 3 ^
^
^
vex next
0 ^
2
5 ^
2
40
1
2
3
4
5
6
^
输出序列,6 1 3 2 4 5
3
2
1
0
4
top
p=NU
LL
3、算法描述
89北京邮电大学自动化学院
? 与 AOV-网相对应的是 AOE-网 (Activity On Edge)即边表示
活动的网。 AOE-网是一个带权的有向无环图，其中顶点表
示事件，弧表示活动，权表示活动持续的时间 。通常 AOE-
网可用来估算工程的完成时间。例如 一个工程有 11项活动，
9个事件。事件 V1—— 表示整个工程开始；事件 V9—— 表示
整个工程结束。
9
8
7
64
5
3
2
1
a6=2
7.6 关键路径
90北京邮电大学自动化学院
? 由于整个工程只有一个开始点和一个完成点，故在正常的情况
下，网中只有一个入度为零的点（称作源点）和一个出度为零
的点（叫做汇点）。
? 对 AOE-网有待研究的问题是：
? （ 1）完成整项工程至少需要多少时间？
? （ 2）哪些活动是影响工程进度的关键？
? 由于在 AOE-网中有些活动可以并行地进行，所以完成工程
的最短时间是从开始点到完成点的最长路径的长度（这里所
说的路径长度是指路径上各活动持续时间之和，不是路径上
弧的数目）。
? 路径长度最长的路径叫做关键路径 。
7.6 关键路径
91北京邮电大学自动化学院
? Ve(j)—— 表示事件 Vj的最早发生时间
? 活动的最迟开始时间 l(i)，这是在不推迟整个工程完成的前提
下，活动 ai最迟必须开始进行的时间。两者之差 l(i)-e(i)意味
着完成活动 ai的时间余量。
? 假设开始点是 v1，从 v1到 vi的最长路径长度叫做事件 vi的最早
发生时间。这个时间决定了所有以 vi为尾的弧所表示的活动
的最早开始时间。
? Vl(j)—— 表示事件 Vj的最迟发生时间
? e(i)—— 表示活动 ai的最早开始时间
? l(i)—— 表示活动 ai的最迟开始时间 l(i)
7.6 关键路径
j k
ai
92北京邮电大学自动化学院
? 例如，从 v1到 v9的最长路
径（ v1,v2,v5,v8，
v9），路径长度是 18，即
v9的最早发生时间是 18。
9
8
7
64
5
3
2
1
a6=2
? 而活动 a6的最早开始时间是 5，最迟开始时间是 8，如果 a6推
迟 3天开始或者延迟 3天完成，都不会影响整个工程的完成。
因此，分析关键路径的目的是辨别哪些是关键活动，以便争
取提高关键活动的工效，缩短整个工期。
7.6 关键路径
? 我们把 l(i)=e(i)的活动叫做关键活动。显然，关键路径上的所
有活动都是关键活动，因此 提前完成非关键活动并不能加快
工程的进度 。
93北京邮电大学自动化学院
j k
ai
? (1)从 Ve(0)=0开始向前递推
11,,) },,()({)( ?????????? njTjijidutiVeM a xjVe i
? 其中,T是所有以第 j个顶点为头的弧的集合
20,,) },,()({)( ?????????? niSjijidu tjVlM i niVl j
? 由上分析可知，辨别关键活动就是要找 e(i)=l(i)的活动。为了
求得 AOE-网中活动的 e(i)和 l(i)，首先应求得事件的最早发生
时间 Ve(j)和最迟发生时间 Vl(j)。设活动 ai用弧 <j,k>表示，其
持续时间记为,dut(<j,k>),则有：
? 其中,S是所有以第 i个顶点为尾的弧的集合
? 如何求 ve(j)和 vl(j)？,需分两步进行
? (2)从 Vl(n)=Ve(n)开始向后递推
? e(i)=ve(j)
? l(i)=vl(k)-dut(<j,k>)
94北京邮电大学自动化学院
求关键路径步骤
? （ 1）输入 e条弧 <j,k>，建立 AOE-网的存储结构；
? （ 2）从源点 v0出发 ve[0]=0，按拓扑有序求其余各顶点的最
早发生时间 ve[i](1?i? n-1)。如果得到的拓扑有序序列中顶
点个数小于网中顶点数 n，则说明网中存在环，不能求关键
路径，算法终止，否则执行步骤（ 3）；
? （ 3）从汇点 vn出发，令 vl[n-1]=ve[n-1]，按逆序拓扑有序求
其余各顶点的最迟发生时间 vl[i]（ 0?i? n-2 ）；
? （ 4）根据各顶点的 ve和 vl值，求每条弧 s的最早开始时间
e(s)和最迟发生时间 l(s)。若某条弧满足条件 e(s)=l(s)，则为
关键活动。
95北京邮电大学自动化学院
? 算法实现
邻接表结点：
typedef struct node
{ int vex; //顶点域
int length;
struct node *next; //链域
}JD;
表头结点：
typedef struct tnode
{ int vexdata;
int in; //入度域
struct node *link; //链域
}TD;
TD g[M]; //g[0]不用
? 以邻接表作存储结构
? 从源点 v1出发，令 ve[1]=0,按拓扑序列求各顶点的 ve[i]
? 从汇点 vn出发，令 vl[n]=ve[n],按逆拓扑序列求其余各顶点的
vl[i]
? 根据各顶点的 ve和 vl值，计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的
关键活动
96北京邮电大学自动化学院
? 点和弧信息，建立其邻接表
9
8
7
64
5
3
2
1
a6=2
? 计算每个顶点的入度
? 对其进行拓扑排序
?排序过程中求顶点的 ve[i]
?将得到的拓扑序列进栈
?按逆拓扑序列求顶点的 vl[i]
?计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动
算法描述
97北京邮电大学自动化学院
9
8
7
64
5
3
2
1
a6=2
v1
v2
v3
v4
v5
v6
v7
v8
v9
顶点 ve vl
0
6
4
5
7
7
16
14
18
0
6
6
8
7
10
16
14
18
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
活动 e l l-e
?
?
?
?
?
?
0 0 0
0 2 2
6 6 0
4 6 2
5 8 3
7 7 0
7 7 0
7 10 3
16 16 0
14 14 0
0 3 3
e(i)=ve(j)
l(i)=vl(k)-dut(<j,k>)
求 ve(i)
求 vl(j)
求 e(i)
求 l(i)
求 l(i)-e(i)
98北京邮电大学自动化学院
? 加快 a8的速度,a8=5 ? a8=4，则
不能使整个工程由 16天缩减成 15
天完成，这是因为另一条关键路
径（ V1,V2,V5,V7,V9）不包
括关键活动 a8。
9
8
7
64
5
3
2
1
a6=2
? 关键活动 a1和 a4。如果 a1=6?a1=5，则整个工程可由 16天缩短
为 15天完成。
? 如果 a1=6?a1=4，整个工程却不能缩短为 14天完成，因为这时关
键路径变成（ V1,V4,V6,V8,V9），路径长度是 15天。
? 所以缩短关键活动的完成时间后,还需要重新计算 AOE-网的关键
路径,只有在不改变 AOE-网的关键路径的前提下,加快包含在所有
关键路径上的关键活动才可以缩短整个工程的完成时间。
99北京邮电大学自动化学院
7.7 最短路径
? 最短路径问题,如果从图中某一顶点 (称为源点 )到达另一
顶点 (称为终点 )的路径可能不止一条，如何找到一条路
径，使得沿此路径各边上的权值总和达到最小。
? 问题解法
?单源最短路径 — Dijkstra算法
?任意顶点对之间的最短路径 — Floyd算法
100北京邮电大学自动化学院
? 给定带权有向图 G和源点 v，求从 v到 G中其余各顶点的最短
路径。例如，下图所示带权有向图 G中从 V0到其余顶点之间
的最短路径。
无
<V0,V2>
<V0,V4,V3>
<V0,V4>
<V0,V4,V3,V5>
1、从某个源点到其余各顶点的最短路径
100 60
30
2010 10
5 50
V1
V2
V3
V4V0
V5 始点 终点 最短路径 长度
v0 v1
v2
v3
v4
v5
10
50
30
60
? 问题：从某顶点出发，沿图的边到达另一顶点所经过的路径
中,各边上权值之和最小的一条路径 —— 最短路径。
101北京邮电大学自动化学院
迪杰斯特拉 (Dijkstra)算法思想
? 如何求得这些路径？
? 迪杰斯特拉提出了一个按路径长度递增的次序产生最短路
径的算法。
? 迪杰斯特拉算法思想,把图中所有顶点分成两组，第一组
包括已确定最短路径的顶点，第二组包括尚未确定最短路
径的顶点，按最短路径长度递增的顺序逐个把第二组的顶
点加到第一组中去，直至从 v0出发可以到达的所有顶点都
包括到第一组中。
? 在这过程中，总保持从 v0到第一组各顶点的最短路径长度
都不大于从 v0到第二组的任何顶点的最短路径长度。
102北京邮电大学自动化学院
求最短路径步骤
? 一开始第一组只包括顶点 v0，第二组包括其他所有的顶点，
v0对应的距离为 0。
? 第二组的顶点对应的距离是这样确定的：若图中有边 <v0，
vi>,vi的距离为此边所带的权值，否则 vi的距离为一个很大
的数（大于所有顶点间的路径长度）。
? 然后每次从第二组的顶点中选一个其距离值为最小的 vm加入
到第一组中。
? 每往第一组加入一个顶点 vm,就要对第二组中的各个顶点的
距离值进行一次修正。 若加进 Vm做中间顶点使从 v0到 vj的最
短路径比不加 vm的路径为短，则要修改 vj的距离值。 修改后
再选距离值最小的顶点加入到第一组中。
103北京邮电大学自动化学院
? 如何求得这些路径？首先，引进一个辅助向量 D，它的每
个分量 D[i]表示当前所找到的从始点 v到每个终点 vi的最短
路径的长度。它的初态为：若从 v到 vi有弧，则 D[i]为弧上
的权值；否则置 D[i]为 ?。显然，长度为
}][{][ VviDjD iiM i n ??
}][{][ SVviDjD iiM i n ???
? 的路径就是从 V出发的长度最短的一条最短路径。此路径
为（ v,vj）。
? 下一条长度次短的路径的长度必是
? 其中,D[i]或是弧上（ v,vi）的权值，或是 D[k]（ vk
?S）和弧（ vk,vi）上的权值之和。
求最短路径步骤
104北京邮电大学自动化学院
算 法
? （ 1）假设用带权的邻接矩阵 arcs来表示带权有向图,arcs[i][j]
表示弧 <vi.vj>上的权值,若 <vi,vj>不存在，则置 arcs[i][j]为 ?.S
为已找到从 v出发的最短路径的终点的集合，它的初始状态为空
集。那么，从 v出发到图上其余各顶点（终点） vi可能达到的最
短路径长度的初值为,D[j]=arcs[Locate Vex(G,V)][i] |vi?V}
? （ 2）选择 vj，使得 D[j]=Min{D[i] |Vi?V-S},vj就是当前
求得的一条从 v出发的最短路径的终点。令 S=S U{j}
? （ 3）修改从 v出发到集合 V-S上任一顶点 vk可达的最短路径长度,
如果 D[j]+arcs[j][k]<D[k],则修改 D[k]为 D[k]=D[j]+arcs[j][k].
? (4) 重复操作（ 2）、（ 3）共 n-1次。由此求得从 v到图上其余
各顶点的最短路径是依路径长度递增的序列。
105北京邮电大学自动化学院
? void Shortpath_DIJ(MGraph G,int v0,PathMatrit &P,ShortPathTable
&D) { //用 Dijkstra算法求有向网的 v0顶点到其余顶点 v的最短路径 P[v]及
其带权长度 D[v]。若 P[v][w]为 TRUE，则 w是从 v0到 v当前求得最短路径
上的顶点。 final[v]为 TRUE当且仅当 v?S，即已经求得从 v0到 v的最短路
径。
迪杰斯特拉算法
? for (v=0; v<G.vexnum;++v){
? final[v]=FALSE; D[v]=G.arcs[v0][v];
? for(w=0; w<G.vexnum;++w) P[v][w]=FALSE;//设空路径
? if (D[v]<INFINITY){P[v][v0]=TRUE;P[v][v]=TRUE;} }//for
? D[v0=0;final[v0]=TRUE;//初始化,v0顶点属于 S集。
? //开始主循环，每次求得 v0到某个 v顶点的最短路径，并加 v到 S集
106北京邮电大学自动化学院
迪杰斯特拉算法
? for (i=1; i<G.vexnum; ++i) { //其余 G.vexnum-1各顶点
? min=INFINTY; //当前所知离 v0顶点的最近距离
? } //for }//ShortwstPath_DIJ
? for (w=0;w<G.vexnum;++w)
? If (!final[w]) //w顶点在 V-S中
? if(D[w]<min){v=w;min=D[w];} //w顶点离 v0顶点更近
? final[v]=TRUE; //离 v0顶点最近的 v加入
? ……
107北京邮电大学自动化学院
迪杰斯特拉算法
? for (i=1;i<G.vexnum;++i){ //其余 G.vexnum-1各顶点
? final[v]=TRUE; //离 v0顶点最近的 v加入 S
? for(w=0;w<G.vexnum;++w) //更新当前最短路径及距离
? }//if }//for }//ShortwstPath_DIJ
? If(!final[w]&&(min+G.arca[v][w]<D[w])){ //修改 D[w]和
P[w],w?V-S
? D[w]=min+G.arcs[v][w];
? P[w]=P[v];P[w][w]=TRUE; //P[w]=P[v]+P[w]
108北京邮电大学自动化学院
?
10
<v0,v2>
?
30
<v0,v4>
100
<v0,v5>
v2
{v0,v2}
?
-------
60
<v0,v2,v3>
30
<v0,v4>
100
<v0,v5>
v4
{v0,v2,v4}
?
-------
50
<v0,v4,v3>
-------
90
<v0,v4,v5>
v3
{v0,v2,v4,v3}
?
-------
-------
-------
60
<v0,v4,v3,v5>
v5
{v0,v2,v3,v4,v5}
?
无
--------
--------
--------
-------
终点 从 V0到各终点的最短路径及其长度
V1
V2
V3
V4
V5
Vj
S
100 60
30
2010 10
5 50
V1
V2
V3
V4V0
V5求最短路径步骤
109北京邮电大学自动化学院
? 人们可能希望找到从源点到某一特定点的终点的最短路径，
但是，这个问题和求解点到其他所有顶点的最短路径一样复
杂，其时间复杂度也是的 O(n2)。
110北京邮电大学自动化学院
2、每一对顶点之间的最短路径
解决办法：
? 方法二,弗洛伊德 (Floyd)算法
? 弗洛伊德算法 思想：逐个顶点试探
? 初始时设置一个 n阶方阵，令其对角线元素为 0，若
存在弧 <vi,vj>,则对应元素为权值；否则为 ?。
? 逐步试着在原直接路径中增加中间顶点，若加入中间
点后路径变短，则修改之；否则，维持原值 。
? 所有顶点试探完毕，算法结束。
? 方法一,每次以一个顶点为源点，重复执行 Dijkstra
算法 n次 —— T(n)=O(n3)
111北京邮电大学自动化学院
? 假设求从顶点 vi到 vj的最短路径。如果从 vi到 vj有弧，则从
vi到 vj存在一条长度为 arcs[i][j]的路径，该路径不一定是最
短路径，尚需进行 n次试探。
? 首先考虑路径（ vi,v0,vj）是否存在（即判别弧（（ vi，
v0），（ v0,vj）是否存在）。如果存在，则比较（ vi，
vj）和（ vi,v0,vj）的路径长度，取长度较短者为从 vi到 vj
的中间顶点的序号不大于 0的最短路径。
? 假设在路径上再增加一个顶点 v1，也就是说，如果（ vi,
?, v1 ）和（ v1,?, vj）分别是当前找到的中间顶点的
序号不大于 0的最短路径，那么（ vi,? v1,?, vj） 就有
可能是从 vi到 vj的中间顶点的序号不大于 1的最短路径。
2、每一对顶点之间的最短路径
112北京邮电大学自动化学院
? 将它和已经得到的从 vi到 vj中间顶点序号不大于 0的最短路
径相比较，从中选出中间顶点的序号不大于 1的最短路径
后，再增加一个顶点 v2，继续进行试探。
? 依此类推。在一般情况下，若（ vi,? vk）和（ vk,?,vj）
分别是从 vi到 vk和从 vk到 vj的中间顶点序号不大于 k-1的最短
路径,则将（ vi,? vk? vj）和已经得到的从 vi到 vj且中间
顶点序号不大于 k-1的最短路径相比较，其长度较短者便是
从 vi到 vj的中间顶点的序号不大于 k的最短路径。
? 这样经过 n次比较后，最后求得的必是从 vi到 vj的最短路
径。按此方法，可以同时求得各对顶点间的最短路径。
2、每一对顶点之间的最短路径
113北京邮电大学自动化学院
算法的基本思想
? 显然,A中记录了所有顶点对之间的最短路径长度。若要
求得到最短路径本身，还必须设置一个路径矩阵 P[n][n]，
在第 k次迭代中求得的 path[i][j]，是从 i到 j的中间点序号不
大于 k的最短路径上顶点 i的后继顶点 。算法结束时，由
path[i][j]的值就可以得到从 i到 j的最短路径上的各个顶
点。
]][[]][[0 jiCjiA ?
]}][[]][[],][[m i n {]][[1 jkAkiAjiAjiA kkkk ???
? 从初始的邻接矩阵 A0开始，递推地生成矩阵序列 A1，
A2,...,An
114北京邮电大学自动化学院
弗洛伊德算法
? void shortpath_FLOYD(int cost[][M],int path[][M],int length[][M],int
n){//用 Floyd算法求有向图 G中各队顶点 v和 w之间德最短路径 P[v][w]及
其带权长度 D[v][w]。若 P[v][w][u]为 TRUE，则 u是从 v到 w当前求得最
短路径上的顶点。
? For (v-0;v,G.vexnum;++w)//
? For (w=0;w<G.vexnum;++w){
? D[v][w]=G.arcs[v][w];
? For (u-0;u,G.vexnum;++u) P[v][w][u]=FALSE;
? IF (D[v][w]<INFINTY){//vw
? P[v][w]=TRUE;P[v][w][u]=TRUE
? }//if } //for
115北京邮电大学自动化学院
弗洛伊德算法
? for(u=0;u<G.vexnum;++u)
? for(v=0;v<G.vexnum;++v))
? for(w=0;w<G.vexnum;++w)
? if(D[v][u]+D[u][w]<D[v][w]) //vuw
? { D[v][w]=D[v][w]+D[u]wj];
? for (i=0;i<G.vexnum;++i)
? P[v][w][i]=P[v][u][i] || P[u][w][i];
? }// if
? }//ShortestPath_Floyd
116北京邮电大学自动化学院
A
C
B
2
6
4
3 11
算法的基本思想
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 1 1
2 0 2
3 1 0
path=
0 4 11
6 0 2
3 ? 0
初始,路径：
AB AC
BA BC
CA
0 1 1
2 0 2
3 0 0
path=
0 4 6
6 0 2
3 7 0
加入 V2,路径,AB ABCBA BC
CA CAB
0 1 2
2 0 2
3 1 0
path=
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
0 1 2
3 0 2
3 1 0
path=
1
3
2
2
6
4
3 11
117北京邮电大学自动化学院
?1,熟悉图的各种存储结构及其构造算法。
? 2,熟练掌握图的两种搜索路径的遍历：遍历的逻
辑定义、深度优先搜索和广度优先搜索的算法。
? 3、熟练掌握最小生成树的普里姆算法。
? 4、熟练掌握如何进行拓扑排序？
? 5、熟练掌握关键路径的计算。
? 6、熟练掌握求最短路径（从某个源点到其余各顶点
的最短路径）的基本思想。
第 7章复习提纲
118北京邮电大学自动化学院
第七章 作业
? 一、单项选择题
? 1、一个 n个顶点的无向图最多有 条边。
? （ A） n （ B） n(n-1) （ C） n(n-1)/2 （ D） 2n
? 2、在一个有向图中，所有顶点的入度之和等于所有顶点的
出度之和的 倍。
? （ A） 1/2 （ B） 1 （ C） 2 （ D） 4
? 3、关键路径是事件结点网络中 。
? （ A）从源点到汇点的最长路径 （ B）最长的回路
? （ C）从源点到汇点的最短路径 （ D）最短的回路
119北京邮电大学自动化学院
? 4、下面不正确的说法是 。
? A、关键活动不按期完成就会影响整个工程的完成时间
? B、任何一个关键活动提前完成，将使整个工程提前完成
? C、所有关键活动都提前，则整个工程提前完成
? D、某些关键活动若提前完成，将使整个工程提前完成。
第七章 作业
120北京邮电大学自动化学院
? 二、填空题
? 1、一个图的 表示法是惟一的，而 表示法
是不惟一的。
? 2、在有 n个顶点的有向图中，每个顶点的度最大可
达 。
第七章 作业
121北京邮电大学自动化学院
? 1、设有向图 G如下图所示，试给
出：
? （ 1）该图的邻接矩阵；
? （ 2）该图的邻接表；
? （ 3）从 V1出发的“深度优先”遍历
序列；
? （ 4）从 V1出发的“广度优先”遍历
序列。
V1
V2
V4 V5
V3
V7V6
V8
第七章 作业
122北京邮电大学自动化学院
? 2、对下图的 AOE网，求出：
? （ 1）每个事件的最早发生时间和最迟发生时间；
? （ 2）每个活动的最早开始时间和最迟开始时间；
? （ 3）画出关键活动组成的图。对哪些活动提速，可使整个
工期提前。
第 7章作业
9
8
7
64
5
3
2
1
a6=2
123北京邮电大学自动化学院
第 7章 上机实习题
? 1、校园导游咨询
? 【 问题描述 】, 设计一个校园导游程序，为来访的客人提
供各种信息查询服务。
? 【 基本要求 】,
? （ 1）设计北邮校园平面图，所含景点不少于 10个。以图
中顶点表示校内各景点，以边表示路径，存放路径长度等
相关信息；
? （ 2）为来访客人提供图中任意景点间的问路查询，即查
询任意两个景点之间的一条最短的简单路径。
? 【 实现提示 】, 一般情况下，校园的道路是双向通行的，
可设校园平面是一无向网。顶点和边均含有相关信息。
124北京邮电大学自动化学院
第七章 上机时间及地点
班 级 时 间 地 点 老 师
0215301～ 302 12.10日 (周五）
14:00~17:00
4－ 328
4－ 328
张志霞
李维成
03501~502 12.11日 (周六）
14:00~17:00
4－ 327
4－ 328
杜 伟
王松月
03503～ 04 12.11日 (周六）
16:00~19:00
4－ 328
4－ 328
王松月
杜 伟
03507~509 12.11(周六）
18:00~22:00
4－ 327
4－ 328
李维成
张志霞
