1
第七章 图
? 图的定义图的定义
? 图的存储结构图的存储结构
? 图的遍历图的遍历
? 图的连通性问题图的连通性问题
? 有向无环图有向无环图
? 最短路径最短路径
? 关键路径关键路径
数
据
结
构
之
图
2
7.1 基本概念
? 图
Graph=(V,R)
V={x|x∈dataobject}
R={VR}
VR={<x,y>|P(x,y) AND (x,y∈V) }
V是顶点的有穷非空集合是顶点的有穷非空集合 ;
VR是两个顶点之间的关系的集合。是两个顶点之间的关系的集合。
顶点：图中的数据元素；
弧、弧头、弧尾： (v1,v2) , v1—弧尾 v2—弧头
2
数
据
结
构
之
图
3
? 有向图： 在图 G中，边是顶点的有序对，每
条边都用箭头指明了方向，若 <V
i
,V
j
>是有向
图中的一条边，则称 V
i
是 尾或初始顶点 ； V
j
是
头 或终端顶点 ，且用从尾到头的箭头表示，
<V
i
, V
j
> 和 <V
j
,V
i
>不同。
? 无向图： 边是顶点的无序对， <Vi,Vj>和
<Vj,Vi>表示同一条边。
V
1
V
2
V
3
V
4
V5
有向图
V
1 V
2
V
3
V
4
V5
无向图
数
据
结
构
之
图
4
? 无向完全 G图：如果在无向图中，任何两个顶点都有
一条边相连接，则称此图为 无向完全图 。含有 n个顶
点，每一个顶点都与其它个 n-1顶点有边，因此，共有
n*(n-1)/2条边。
? 有向完全图：在有向图 G中，任何两个顶点都有方向
相反的两条弧线连接，若图 G中含有个 n顶点，则共有
n*(n-1)条弧 。
V
1 V
2
V
3
V
4
V5
无向完全图
V
1 V
2
V
3
V
4
V5
有向完全图
3
数
据
结
构
之
图
5
? 网： 如果图 G(V,{E})中每条边都赋有反映这
条边的某种特性的数据，则称此图 G是一个 网 ，
其中与边相关的数据称为该边的 权 ，权所反
映的特性，由具体问题决定，例于两点之间
的距离，时间，代价。
网
V
1
V
2
V
3
V
4
V5
5
3
46
8
7
1
2
V
1
V
2
V
3
V
4
V5
4
5
8
6
3
数
据
结
构
之
图
6
?子 图：假设有两个图 G=(V， {E})和图 G
’
=(V
’
，
{E
’
})，如果 V
’
?V，且 E
’
?E, 则称 G
’
为 G的子图。
V
1
V
2
V
3
V
4
V5
无向图
子图
V
2
V
1
V5
V
1
V5
V
4
V
3
V
2
V
2
V
1
V
2
V
1
V5
V
3
?邻接点： 对于无向图 G=(V,{E})，如果边 <V,V
’
>∈E,
则称顶点 V和 V
’
互为邻接点，边 (V,V
’
)依附于顶点 V和
V
’
。
4
数
据
结
构
之
图
7
?度： 顶点 V的度是和 V相关联的边的数目，记为
TD(V)。
?入度： 如果顶点 V是有向图的一个顶点，则称以 V为
头的弧的数目为 V的入度，记为 ID(V)。
?出度 ：如果顶点 V是有向图的一个顶点，则称以 V为
尾的弧的数目为 V的出度，记为 OD(V)。
?有向图顶点的度 ：顶点 V的度 TD(V)=ID(V)+OD(V)。
推论 ： 如果顶点 V
i
的度为 TD（ V
i
），那么有 n个顶点，
e条边或弧的图，满足如下关系
∑
=
=
n
i
i
vTDe
1
)(
2
1
数
据
结
构
之
图
8
?路径：图中从顶点 V到顶点 V
’
的路径是顶点
的序列（ V=V
i,0
, V
i,1
, …, V
i,m
= V
’
），其中
（ V
i,j-1
, V
i,j
)∈E， 1≤ j ≤m。
?路径的长度：路径上所含边的数目。
?回路：第一个顶点和最后一个顶点相同的路
径称为回路或环。
?简单路径：序列中顶点不重复出现的路径称
为简单路径。
?简单回路：除第一个和最后一个顶点之外，
其它顶点不重复出现的回路称为简单回路或环。
5
数
据
结
构
之
图
9
?连通： 在无向图 G中，若从顶点 V到顶点 V
’
有路径，
则称 V和 V
’
是连通的。
?连通 图： 若对于图中任意两个顶点 V
i
， V
j
∈V
都是连通的，则称是连通图。
?连通分量：指无向图中极大连通子图。
?强连通图：在有向图中，如果对每一对 V
i
， V
j
∈V ， V
i
≠V
j
，从 V
i
到 V
j
和从 V
j
到 V
i
都存在路径，则
称 G是强连通图。有向图 G的极大强连通子图称为
强连通分量。
12
3
4
1
2
3
4
不是强连通图
两个强连通分量
数
据
结
构
之
图
10
?生成树生成树
定义：定义： 设无向图设无向图 G是含有是含有 n个顶点个顶点 的连通图，的连通图， 则图则图 G
的生成树是含有的生成树是含有 n个顶点个顶点 ，且只有，且只有 n-1条边条边 的的 连通连通 子图子图
三要素：三要素：
n个顶点个顶点
n-1条边条边
连通连通
生成树生成树 n-1条边条边
极小连通子
图，若再加
一条边，必
构成环
6
数
据
结
构
之
图
11
图的基本操作
LOC-VERTEX（ G， v）： 顶点定位函数；
GET-VERTEX（ G， I）： 取顶点函数；
FIRST-ADJ（ G， v）： 求第一个邻接点函数；
NEXT-ADJ（ G， v， w）： 求下一个接点函数；
INS-VERTEX（ G， u）： 插入顶点操作；
INS-ARC（ G， v， w）： 插入弧操作；
DEL-VERTEX（ G， v）： 删除顶点操作；
DEL-ARC（ G， v， w）： 删除弧的操作。
数
据
结
构
之
图
12
7.2 图的存储结构
? 邻接矩阵：用一个二维数组来表示图中的相邻关系。
设图 G=（ V， VR）有 n≥1个顶点，则 G的邻接矩阵是
按如下定义的 n阶方阵：
1，若（ Vi , Vj )或 <Vi , Vj>∈ VR
A[i， j]=
0，反之 无向图G2的邻接矩阵
0 1 1 0 0 1 0 1 0
A1= 0 0 0 0 1 0 1 0 1
0 0 0 1 A2= 0 1 0 1 1
1 0 0 0 1 0 1 0 0
有向图G1的邻接矩阵 0 1 1 0 0
7
数
据
结
构
之
图
13
例：分别写出下面图的邻接矩阵。
1
2
3
4
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0
1
2
3 4
0 1 0 0
0 0 1 0
0 0 0 1
0 1 0 0
数
据
结
构
之
图
14
? 邻接矩阵存储的特点
?无向图的邻接矩阵是对称的，对有 n个顶
点的无向图只需存入下三角矩阵，即需要
n(n+1)/2 个存储单元；
?而有向图的邻接矩阵不一定对称，对有 n
个顶点的有向图需要 n*n个单元来存储邻
接矩阵；
?另外用向量来存储顶点的有关信息；
8
数
据
结
构
之
图
15
?求顶点的度
?对无向图， Vi的度数 =邻接矩阵第 i 行元
素之和
?对有向图， Vi的出度 =第 i 行元素之和
Vi的入度 =第 i 列元素之和
n n
TD(Vi)=∑ A[i,j]=∑ A[j,i]
j=1 j=1
TD(Vi)=OD(Vi)+ID(Vi)
n n
= ∑ A[i,j]+∑ A[j,i]
j=1 j=1
数
据
结
构
之
图
16
? 网的邻接矩阵
wi, j，若（ Vi , Vj )或 <Vi , Vj>∈ VR
A[i， j]= 0 , ( i = j )
∞，反之
05 ∞ 7 ∞∞
∞ 0 4 ∞∞∞
8 ∞ 0 ∞∞ 9
∞∞5 0 ∞ 6
∞∞∞5 0 ∞
3 ∞∞∞ 1 0
V1 V2
V3
V4
V6
V5
1
5
3
5
4
8
7
9
6
5
9
数
据
结
构
之
图
17
? 图的数组（邻接矩阵）存储表示邻接矩阵
#define MaxData 35000
#define VerNum 20
/* 有向图，有向网，无向图，无向网 */
typedef enum{DG, DN, UDG, UDN}GraphKind;
typedef char VertexType;
typedef int VRType; /*顶点关系 0/1 或 “权值 ”
typedef struct{ VRType adj;
InfoType *information; }ArcType;
typedef struct{
VertexType vexs[VerNum];
ArcType arcs[VerNum][VerNum];
int vernum, arcnum;
GraphKind kind; } MGraph;
数
据
结
构
之
图
18
采用邻接矩阵表示法，构造图
Status CreateGraph(MGraph &G){
scanf(&G.kind);
switch(G.kind){
case DG: return CreateDG(G);
case DN: return CreateDN(G);
case UDG: return CreateUDG(G);
case UDN: return CreateUDN(G);
default: return ERROR; } }
10
数
据
结
构
之
图
19
采用邻接矩阵表示法，构造无向网
Status CreateUDN(MGraph &G){
scanf(&G.vexnum,&G.arcnum,&Infoflag);
for(i=0;i<G.vexnum;i++) scanf(&G.vexs[i]);
for(i=0;i<G.vexnum;i++) / *邻接矩阵初始化 */
for(j=0;j<G.vexnum;j++)
if (i != j) G.arcs[i][j]={MaxData, NULL};
else G.arcs[i][j]={0, NULL};
for(k=0;k<G.arcnum;k++){
scanf(&v1,&v2,&w);
i=LocateVex(G,v1); j=LocateVex(G,v2);
G.arcs[i][j].adj=w; /*弧 <v1,v2>的权值 */
if(infoflag) input(*G.arcs[i][j].information);
G.arcs[j][i]=G.arcs[i][j]; }
return OK; }
数
据
结
构
之
图
20
?邻接链表
? 图的邻接链表存储结构是一种顺序分配和链
式分配相结合的存储结构：一部分是链表；
另一部分是向量。
? 链表部分：每个顶点对应一个链表，共有 n
个链表；
? 向量部分：用于存储 n个链表的表头结点。
V1 V2
V4 V5
V3
0 v1
1 v2
2 v3
3 v4
4 v5
3 1 ^
2 0 ^
2 1 ^
4 3
4 2 0 ^
1 ^
11
数
据
结
构
之
图
21
例: 用邻接表和逆邻接表的形式描述下面的
有向图
1
2
34
邻接表
V1
V2
V3
V4
1
2
3
1
^
^
^
^
0
1
2
3
逆邻接表
V1
V2
V3
V4 2
3
1
^
^
^
0
0
1
2
3
^
数
据
结
构
之
图
22
? 图的邻接链表存储表示
typedef struct Arc{ //弧结点类型
int adjvex ;
InfoType *info;
struct Arc *nextarc;
}ArcNode;
typedef struct Vnode{ // 顶点向量类型
VertexType data;
ArcNode *firstarc;
}Vnode;
typedef struct{
Vnode vertices[VerNum];
int vernum, arcnum;
GraphKind kind; } ALGraph;
12
数
据
结
构
之
图
23
?有向图的十字链表表示
? 在十字链表中，对应于有向图中每一条弧有一
个结点，对应每个顶点也有一个结点。
? 十字链表可以看成邻接矩阵的链式存储
tailvex headvex hlink tlink
弧结点
Data firstin firstout
顶点结点
V1 V2
V3 V4
V1
V2 ^
V3
V4
0 1 ^ 0 2 ^ ^
2 3 ^ ^
3 0 ^ ^
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
数
据
结
构
之
图
24
? 用 C语言描述的十字链表：
#define MAX_VERTEX_NUM 20
typdef struct ArcBox{
int tailvex, headvex; //该弧的尾和头顶点的位置
struct ArcBox *hlink, *tlink; //弧头及弧尾相同的弧的链域
InfoType *info; //该弧相关信息的指针
}ArcBox;
Typedef stuct VexNode{
VertexType data;
ArcBox *firstin, *firstout; //分别指向该顶点第一条入弧和出弧
}VexNode;
Typedef struct{
VexNode xlist[MAX_VERTEX_NUM]; //表头向量
int vexnum, arcnum; //有向图的当前顶点数和弧数
}ALGraph;
13
数
据
结
构
之
图
25
? 无向图的邻接多重表
? 在邻接多重表中，每一条边用一个结点表示，
对应每个顶点也有一个结点。
? 在邻接表中同一条边用两个结点表示，而在邻
接多重表中只有一个结点。
? 邻接多重表的结构和类型说明参见教材 P167
mark ivex ilink jvex jlink
弧结点
Data firstedge
顶点结点
数
据
结
构
之
图
26
例：用邻接多重表的形式描述下面的无向图。
3
4
12
5
无向图 G的邻接多重表
01
12
23
43
54
01
2
1
41
0
3
23
24
^^
^^^
14
数
据
结
构
之
图
27
7.3 图的遍历
? 图的遍历：
从图中某一
顶点出发访
遍图中其余
顶点，且使
每一个顶点
仅被访问一
次。
i=0
V1 V2
V4 V5
V3
0 v1
1 v2
2 v3
3 v4
4 v5
3 1 ^
2 0 ^
2 1 ^
4 3
4 2 0 ^
1 ^
数
据
结
构
之
图
28
? 深度优先遍历：类似于树的前序遍历；
? (1)访问指定的某顶点 V，将 V作为当前顶点
? (2)将该顶点作为当前顶点，访问当前顶点的
下一未被访问过的邻接点
? (3)重复 (2)，直到当前顶点的所有邻接点都被
访问过。
? (4)沿搜索路径回退，退到尚有邻接点未被访
问过的某顶点，将该顶点作为当前顶点 ,重复
以上步骤 ,直到所有顶点被访问过为止。
15
数
据
结
构
之
图
29
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
解：该图用邻接表表示如下：
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
12
03 4
05 6
17
17
2 7
2 7
3 4
5 6
0
1
2
3
4
5
6
7
其深度优先搜索结果为 ： V
1
， V
2
， V
4
， V
8
， V
5
， V
6
， V
3
， V
7
。
例：用邻接表的形式表示下面的图，并写出其深
度优先搜索结果。
数
据
结
构
之
图
30
Void DFSTraverse(Graph G ){
for( v=0 ; v<G.vexnum; ++v)
visited[v]=False;
for(v=0 ; v<G.vexnum ; ++v)
if( visited[v]==False) DFS(G, v);
}
void DFS(Graph G , int v){
visited[v]=True ; Printvex(v);
for( w=FirstAV(G,v); w>=0; w=NextAV(G,v,w))
if(visited[w]==False) DFS(G,w);
}
时间复杂度： Page 169
16
数
据
结
构
之
图
31
0 v1
1 v2
2 v3
3 v4
4 v5
3 1 ^
2 0 ^
2 1 ^
4 3
4 2 0 ^
1 ^
void DFS(Graph G , int v){ visit[v]=True ; Printvex(v);
for( w=FirstAV(G,v); w>=0 ; w=NextAV(G,v,w))
if(visit[w]==False) DFS(G,w); return ;}
Print v1
w=3
w=1
w=^
return;
G, 3
Print v4
w=2
w=0
w=^
return;
G, 2
Print v3
w=4
w=3
w=1
w=^
return;
G, 4
Print v5
w=2
w=1
w=^
return;
G, 1
Print v2 ; w=4,
w=2, w=0, w=^
return ;
G, 0
DFS 递归 算
法示意图
数
据
结
构
之
图
32
? 广度优先遍历：类似于
树的按层次遍历，步骤：
? 访问 v1后，依次访问
与 v1相邻的所有顶点
w1,w2,......,wt ;
? 再按 w1,w2,...,wt的顺
序，访问其中每一个
顶点的所有未被访问
过的邻接顶点，以此
类推，直到图中所有
顶点都被访问过为止。
V1
V2
V5
V8
V4
V7
V6
V3
17
数
据
结
构
之
图
33
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
解：仍采用前面的存储结构，
其广度优先搜索结果为：
V
1
， V
2
， V
3
， V
4
， V
5
，
V
6
， V
7
， V
8
。
例：写出下图广度优先搜索结果。
数
据
结
构
之
图
34
广度优先非递归遍历算法描述
void BFSTraverse(Graph G){
for(v=0;v<G.vexnum ; v++) visited[v]=False ;
InitQueue(Q);
for(v=0 ; v<G.vexnum ; ++v)
if(visited[v]==False){
EnQueue(Q ,v);
while( 队列不空 ){ DeQueue( Q, u) ;
if(!visited[u]){visited[u]=True ; PrintVex(u);
for(w=FirstAV(G,u); w; w=NextAV(G,u,w))
if(visited[w]==False) EnQueue(Q,w);
}//if }//while
}//if }//end
18
数
据
结
构
之
图
35
7.4 生成树和最小生成树
? 生成树：设 G=(V,E)为连通图，则从图中任一顶点
出发遍历图时，必定将 E分成两个集合 T和 B，其中
T是遍历图过程中走过的边的集合， G’=(V,T)是 G的
极小连通子图 ，是 G的一棵生成树。
? 图的生成树不是唯一的：
?深度优先生成树；
?广度优先生成树。
有 n个顶点的连通图至少有 条边，
有 n个顶点的连通图生成树只有 条边。
数
据
结
构
之
图
36
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
深度优先生成树
V
1
V
2
V
3
V
4
V
5
V
6
V
7
V
8
广度优先生成树
19
数
据
结
构
之
图
37
? 最小生成树
? 把边上赋以权值的图称为网或带权图；
? 网的最小生成树就是边上权值之和为最小的生
成树； 权值可以是：造价（费用）、路程、时
间等 。
? 构造网的最小生成树要解决好以下两个问题：
?尽可能选取权值小的边，但不能构成回路；
?选取 n-1条恰当的边以连接网的 n 个顶点。
? 最小生成树的性质 ( MST性质 )：
假设 G=（ V， E）是一个连通网， T’是顶点集 V
的一个非空子集。若 (u ,w)是一条具有最小权值的边，
其中 u∈T’, w∈V-T’，则必存在一棵包含边 ( u ,w)的
最小生成树 T=(T’,E’)。
数
据
结
构
之
图
38
? 最小生成树的实用例子最小生成树的实用例子
例 1： N台计算机之间建立通讯网
顶点表示 computer
边表示通讯线
权值表示通讯线的代价（通讯
线长度， computer间距离等）
要求：
① n台计算机中的任何两台能通过网进行通讯；
② 使总的代价最小。--求最小生成树[T]
20
数
据
结
构
之
图
39
例 2： 邮递员送信线路 [T]
顶点表示投递点
边表示街道
权值表示街道的长度
要求：
① 完成n个投递点的投递；
② 使总路径长度最短, 即求最小生成树[T]
数
据
结
构
之
图
40
? 求最小生成树的两种常用的算法
? 普里姆（ Prim）算法：假设 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的
最小生成树。
21
数
据
结
构
之
图
41
1
2
3
4
5
6
6
1
5
55
3
64
2
6
1
1
3
1
6
1
3
1
4
4
6
1
3
1
4
2
2
5
3
5
4
6
1
3
1
4
2
5
4
6
1
3
1
4
2
2
数
据
结
构
之
图
42
Prim算法实现
为实现 Prim算法，需附设一个辅助数组 closedge，以
记录从 U到 V-U具有 最小代价 的边。
顶点 u , u∈U
closedge[i-1]包含两个域：
权值 , (u,vi)边上的权值
eg： U=(v1,v6,v5), V-U=(v2,v3,v4), closedge[1]={v1,5}
closedge[2]={v6, 6}, closedge[3]={v5, 4}
V1 V2
V3
V4
V6
V5
1
5
3
5
4
8
7
9
6
5
22
数
据
结
构
之
图
43
V1
V2
V3
V4
V6
V5
1
5
3
5
4
8
7
9
6
5
0 1 2 3 4 5 U V-U k
adjvex
Lcost
0
v1
5
v1
8
v1
7
∝
v1
3
v1 v2,v3,v4,
v5,v6
5
adjvex
Lcost
0
v1
5
v1
8
v6
6
v6
1
0
v1,v6 v2,v3,v4,
v5
4
adjvex
Lcost
0
v1
5
v1
8
v5
4
0
0
v1,v6,v5 v2,v3,v4 3
adjvex
Lcost
0
v1
5
v4
5
0
0
0
v1,v6,v5,
v4
v2,v3 1
adjvex
Lcost
0
0
v4
5
0
0
0
v1,v6,v5,
v4,v2
v3 2
adjvex
Lcost
0
0
0
0
0
0
v1,v2,v3,
v4,v5,v6
0 5 8 7 ∝ 3
5 0 5 ∝∝∝
8 5 0 5 ∝ 9
7 ∝ 5 0 4 6
∝∝∝ 4 0 1
3 ∝ 9 6 1 0
数
据
结
构
之
图
44
V1
V2
V3
V4
V6
V5
1
3
4
5
5
V1
V2
V3
V4
V6
V5
1
5
3
5
4
8
7
9
6
5
23
数
据
结
构
之
图
45
void MinST_Prim( Mgraph G, VertexType u){
k=LocateVex(G, u);//求顶点的下标
for( j=0; j<G.vexnum ; j++) //初始化
closedge[j]={ u , G.arcs[k][j].adj };
closedge[k].lowcost=0;
for( i=1 ; i<G.vexnum ; ++i){//取大于 0的最小
k=minimum(closedge);// 权值边的顶点下标
printf( closedge[k].adjvex , G.vex[k]);
closedge[k].lowcost=0;
for( j=0 ; j<G.vexnum ; ++j)
if(G.arcs[k][j].adj<closedge[j].lowcost)
closedge[j]={G.vexs[k],G.arcs[k][j].adj};
}//for// }//end O( n*n)
Prim算法描述以二维数组表示网的邻接矩阵
数
据
结
构
之
图
46
? 克鲁斯卡尔（ Kruskal）算法
?设连通网 N含有 n个顶点， T是 G的最小生成
树 ,E(T)是最小生成树边的集合， E(T)?E(N)，
其初值为空；
?当 E(T)中的边数小于 n-1时，重复做下列操作：
?从 E(G)中选取权值为最小的边 (u ,w);
?从 E(G)中删去 (u , w);
?如果 (u , w)不和 E(T)中的边构成回路，则将 (u,w)加
到 E(T)中去，否则舍去边 (u , w)。
假设网中有 e条边，算法的时间复杂度可以为
O(e*log e)，因此，它适用于边稀疏的网
24
数
据
结
构
之
图
47
例：采用克鲁斯卡尔(Kruskal)
算法求下图的最小生成树。
1
2
3
4
5
6
6
1
5
55
3
64
2
6
1
2
5
3
6
4
1
1
2
5
3
6
4
1
2
1
2
5
3
6
4
1
2
3
1
2
5
3
6
4
1
2
3
4
1
2
5
3
6
4
1
2
3
4
5
数
据
结
构
之
图
48
V1 V2
V3
V4
V6
V5
11
113
5
4
8
7
9
6
15
V2 V3 1
V1 V2 5
V4 V5 4
V1 V3 6 ... V3 V4 15 ^
N
V1 V2 V3 V4 V5 V6
E( T )={ }
V1 V2 V3 V4 V5 V6
E( T )={(v2,v3) }// 1
V1 V2 V3 V4 V5 V6
E( T ) ={(v2,v3),
(v4,v5) }// 1 ,4
V1 V2 V3 V4 V5 V6
E( T ) ={ (v2,v3) ,
(v4,v5) , (v1,v2) }
//1,4,5
25
数
据
结
构
之
图
49
V1 V2
V3
V4
V6
V5
11
113
5
4
8
7
9
6
15
V1 V2
V3
V4
V6
V5
1
5
4
8
7
数
据
结
构
之
图
50
7.5 拓扑排序
? 顶点表示活动的网（ AOV-网）
? 用顶点表示活动，用弧表示活动间的优先关系
的有向图，称为 AOV-网。
? 例如：下图中， v1表示“学习数据结构”
v2表示“期末总复习”
v3表示“出考题、印试卷”
v4表示“期末考试”
拓扑排序结果为：
v1 , v2 , v3 , v4
或 v1 , v3 , v2 , v4
V1
V2
V4
V3
26
数
据
结
构
之
图
51
有向图中的弧 < Vi , Vj > 表示 Vi ≤ Vj（可以
理解为 Vi 领先于 Vj）
定义：对于一个 AOV网，构造其所有顶点的线性序
列，使此序列不仅保持网中顶点间原有的先后关
系，而且使得原来没有先后关系的顶点之间也建
立起人为的先后关系，这样的线性序列称为拓扑
有序序列。构造 AOV网的拓扑有序序列的操作
称为拓扑排序。
V1
V2
V4
V3
偏序
V1
V2
V4
V3
全序
数
据
结
构
之
图
52
拓扑排序
的方法：
C1
C4
C2
C12
C9
C10
C6
C11
C3
C5
C7
C8
课程编号 课程名称
C1 程序设计基础
C2 离散数学
C3 数据结构
C4 汇编语言
C5 设计和分析
C6 计算机原理
C7 编译原理
C8 操作系统
C9 高等数学
C10 线性代数
C11 普通物理
C12 数值分析
(1)在有向图中选一个没
有前驱的顶点且输出之；
(2)从图中删除该顶点和
所有以它为尾的弧
27
数
据
结
构
之
图
53
? 拓扑排序算法
? 采用邻接表作有向图的存储结构，且在头结
点中增加一个存放顶点入度的数组 (indegree)。
? 入度为零的顶点即为没有前驱的顶点，删除
顶点及以它为尾的弧的操作，则可换以弧头
顶点的入度减 1 来实现。
? 若拓扑排序的结果
输出的顶点数〈 有向图中的顶点数
则该有向图有回路。
数
据
结
构
之
图
54
Status TopiSort( ALGraph G ){
FindInDegree(G , indegree) ; InitStack(S) ;
for(i=0; i<G.vernum ;i++)
if(indegree[i]==0) Push( S, i );
count = 0;
while(栈不空） {
Pop(S,i);printf(i,G.vertices[i].data);++count;
for(p=G.vertices[i].firstarc; p ; p=p->nextarc){
k=p->adjvex;
if((--indegree[k])==0) Push(S, k);}//for }//whi
if(count<G.vexnum) return ERROR; // 回路
else return OK; }//end O( n+e )
28
数
据
结
构
之
图
55
? 关键路径 —AOE网
? AOE网：顶点表示事件，是边表示活动，权
表示活动持续的时间的带权有向无环图。
? 关键路径：从源点到汇点的 路径长度 最长的
路径。关键路径上的所有活动均是关键活动。
? 基本术语：
1 vi事件的最早发生时间 ve(i) 正向 取最大值
2. vi事件的最迟发生时间 vl(i) 逆向 取最小值
3. 活动 ai 的最早开始时间：（弧 <j , k>表示 ai）
e( i ) = ve( j )
4. 活动 ai的最迟开始时间 ： l(i)=vl(k)-ai
数
据
结
构
之
图
56
? 求关键路径的算法
? 输入 e条弧 <j, k>，建立 AOE-网的存储结构；
? 从源点 v0出发，令 ve[0]=0，按拓扑有序求其
余各顶点的最早发生时间 ve[i](0<i<n)。如果
有回路，算法终止；否则继续；
? 从汇点 vn出发，令 vl[n-1]=ve[n-1]，按逆拓扑
有序求其余各顶点的最迟发生时间 vl[i] (n-
1>i>1);
? 根据各顶点的 ve和 vl的值，求每条弧 s的最早
发生时间 e(s)和最迟发生时间 l(s)。若某条弧满
足条件 e(s)=l(s)，则为关键活动。
? e(i) = l(i) 的所有活动 ai是关键活动，关键路径
上的所有活动都是关键活动。
29
数
据
结
构
之
图
57
例：采用上面的算法求下图的关键路径。
解 ：用 Ve[i]表示顶点 i最早发生的时间， Vl[i]表示顶点 i最迟发生的
时间， e[s]表示弧 s最早开始时间， l[s]表示弧 s最迟开始时间。这
样便可以根据上面介绍的算法得到下面的这样一张表：
a4=3
1
2
3
4
5
6
a1=3
a2=2
a5=4
a3=2
a6=3
a7=2
a8=1
数
据
结
构
之
图
58
1
2
3
4
5
6
a4=3
1
2
3
4
5
6
a1=3
a2=2
a5=4
a3=2
a6=3
a7=2
a8=1
0
3
2
6
6
8
1
2
3
4
5
6
0
4
2
7
6
8
顶点最早发生的时间 顶点最迟发生的时间
30
数
据
结
构
之
图
59
V1 0 0
V2 3 4
V3 2 2
V4 6 6
V5 6 7
V6 8 8
a1 0 1 1
a2 0 0 0
a3 3 4 1
a4 3 4 1
a5 2 2 0
a6 2 5 3
a7 6 6 0
a8 6 7 1
Ve V1
e l 1-e
顶点
活动
正推 倒推
根据上表， l[s]-e[s]等于 0的活动有 a2,a5,a7，因此
a2,a5,a7为关键活动。
数
据
结
构
之
图
60
Status ToplOrder(ALgraph G, Stack &T){//有向网 G采用
邻接链表存储 , 求各顶点的最早发生时间 ve(全局变量 )
FindInDegree(G,indegree); InitStack(T);InitStack(S);
for(i=0; i<G.vernum; i++) if(indegree[ i ]==0) Push(S, i);
count=0; ve[0……G.vernum-1]=0;
while(!StackEmpty(S)){ Pop(S, j); Push(T, j) ; count++;
for(p=G.vertices[ j].firstarc; p; p=p->next){
k=p->adjvex;
if(--indegree[k]==0) Push(S, k);
if(ve[ j]+*(p->info) > ve[k])
ve[k]=ve[j]+*(p->info); }//for
}//while
if(count<G.vernum) return ERROR;
else return OK;
}//end of TopolOrder
31
数
据
结
构
之
图
61
Status CriticalPath(ALGraph G){
if( !ToplOder(G,T )) return EEROR;
Pop(T,j); vl[ j ]=ve[ j ];
while( !StackEmpty(T)){
Pop(T, j); vl[j]=Maxdata;
for(p=G.vertices[ j].firstarc; p; p=p->nextarc){
k=p->adjvex ; w =*(p->info);
if( (vl[k]-w)<vl[j]) vl[j]=vl[k]-w ; }//for
}//while
for(j=0; j<G.vexnum; j++)
for( p=G.vextices[j].firstarc; p ; p=p->nextarc){
k=p->adjvex; w=*(p->info);
ee=ve[ j];el=vl[k]-w;
if (ee==el) printf( <j, k> , w ); }
} // End Of CriticalPath
数
据
结
构
之
图
62
? 通常网中关键路径有多条，必须提高
同时在几条关键路径上的活动的速度
才有效，并且关键活动的速度提高是
有限的。
1
2
3
4
5
6
7
8
9
6
4
5
1
1
2
9
7
4
2
4
32
数
据
结
构
之
图
63
? 最短路径
? 从某个源点到其余各顶点的最短路径
? 迪杰斯特拉（ Dijkstra）提出：按路径长度递
增的次序产生最短路径的算法。
? 数组 D[ n ]：存放当前所能找到的源点 v到各顶
点的最短路径长度。
? 数组 P[n]： P[i] 存放源点 v到 vi顶点的最短路径
所经历的最后一个顶点号。
? 最短路径的产生： S={v};
第一条： D[j]=Min{D[ i ] }, 则 (v,vj)是一条
最短路径； S={v,vj};
下一条：假定终点是 x，则最短路径 或者
是弧 (v,x)或者是 (v,vj,x):中间只经过 S 中的
顶点而最后到达顶点 x的路径。 S={v,vj,x};
数
据
结
构
之
图
64
例：有向图如下图，求V 0到其它各顶点的最短路径。
解 ： 根据上面的算法，其求解过程如下表所示。
终点 从 V0到各终点的弧值和最短路径
V1
V2
V3
V4
V5
Vj
∞∞∞∞
∞
10
(V0,V2)
60
(V0,V2,V3)
50
(V0,V4,V3)
30
(V0,V4)
30
(V0,V4)
100
(V0,V5)
100
(V0,V5)
90
(V0,V4,V5)
60
(V0,V4,V3 ,V5)
V2 V4 V3 V5
０
１
２
3
4
5
100
10
5
50
30
10
60
20
33
数
据
结
构
之
图
65
单源点最短路径算法 (采用邻接矩阵存储带权有向图 )
1. S={v }, k= LocateVex(G,v) ;
for (i=0;i<G.vernum;i++)
{ D[i]=G.arc[ k ][i];P[i]=k; final[i]=False;}
final[ k ]=True;
2. D[j]=Min{D[ i ]}; final[j]=True; //S=S U j;
3. 修改从 v出发到集合 V-S上任一顶点 vk可达到的最
短路径长度。
For(w=0; w<G.vexnum;w++)
If (!final[w] && D[j]+G.arc[j][w] <D[w] ) {
D[w]= D[j]+G.arc[j][w] ； P[w]= j; }
4. 重复操作 2、 3共 n-1次
******** 时间复杂度： O(n*n) **********
数
据
结
构
之
图
66
? 本章重点
? 与图有关的一些基本概念。
? 图的存储结构：邻接矩阵、邻接表
? 图的遍历：深度、广度遍历
? 最小生成树。
? 拓扑排序
? 关键路径及最短路径。
34
数
据
结
构
之
图
67
《数据结构》最终考试题型
一、基本概念题
二、基本操作算法题
三、算法思想手工演算题
四、编写算法题
