,数据结构,
第七章 图
(重点 )
第七章 图第 2页主要内容
图的概念
图的存储结构数组表示法 —— 邻接矩阵邻接表表示法十字链表表示法邻接多重表表示法
图的遍历深度优先搜索广度优先搜索第七章 图第 3页主要内容
图的连通性问题无向图的连通分量和生成树构造最小生成树的 Prim算法构造最小生成树的 Kruskal算法
有向无环图
拓扑排序
关健路径
最短路径第七章 图第 4页第七章 图
内容和要求图及其有关的基本概念、图的存储结构及其图的遍历，
最短路径、拓扑排序的关健路径，动态存储管理。要求获得有关图结构及其应用方面的初步知识和经验。理解图及其有关的基本概念，图的存储方法，熟悉遍历图的深度优先（
DFS）和广度优先（ BFS）的搜索算法，了解最短路径、拓扑排序、关健路径的方法及算法的基本思想。
重点图的三种常用的存储表示,DFS法和 BFS法。难点是图的邻接多重存储表示,DFS法和 BFS法，最短路径。
第七章 图第 5页什么是图图形结构是一种较 线性表结构 和 树形结构 更为复杂的 非线性数据结构 。 在人工智能、工程、数学、物理、
化学、计算机科学等学科领域中，图形结构均有着广泛的应用。
线性表结构,数据元素即结点之间仅有线性关系。
树形结构,数据元素之间具有明显的层次关系。每层中的结点可允许有若干个孩子结点，但 仅 允许有一个双亲结点（前趋）。
图形结构,数据元素之间的关系是 任意的,图中任意两个结点之间都可能相关。
事实上，树形结构是图形结构的一种特殊情况。
图的概念第七章 图第 6页图常用来解决的几类主要问题
1,模拟计算机与通信网络的联接；
2,表示一张地图的一组坐标以及坐标之间的距离，以求得最短路径；
3,模拟交通网络的流量；
4,寻找从开始状态到目标状态的路径，如人工智能问题求解；
5,模拟计算机算法，显示程序状态的变化；
6,为复杂活动各子任务的完成寻找顺序，如大型建筑的建造；
… … … …
图的概念第七章 图第 7页定义,图是一种数据结构，它的形式化定义为
Graph=(V,R)
其中
V={x|x∈ dataobject}
R={VR}
VR={＜ x,y＞ | P(x,y)∧ (x,y ∈ V)}
可以简记为
G=（ V,E）
其中 V是顶点的有穷非空集合,E是 V中顶点的偶对（称为边）的有穷集。
通常亦可将图 G的顶点集和边集分别记作 V(G)和
E(G)。
若 E(G)为空集，则表示图 G仅有顶点而没有边。
图的定义第七章 图第 8页示例 1 有向图 G1和无向图 G2
G1
G2
图的定义
V(G1)={v1,v2,v3,v4}
E(G1)={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
V(G2)={v1,v2,v3,v4,v5}
E(G2)={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
V1 V2
V3 V
4
V1 V2
V4 V5
V3
第七章 图第 9页顶点,图中的数据元素。
弧,有向边，用以尖括号括起来的 有序对 <vi,vj>表示。
弧尾,有向边 <vi,vj>的始点 vi。
弧头,有向边 <vi,vj>的终点 vj。
有向图,图 G中每条边都是有向边（ 弧 ）。
无向图,图 G中每条边都是没有方向的，这些边用以
(vi,vj )形式的 无序对 表示 。
图的术语
V1 V2
V3 V
4
V1 V2
V4 V5
V3
第七章 图第 10页图的顶点数 n和边数 e的关系,对有向图,0≤e≤n(n-1)；对无向图,。
有向完全图,恰有 n(n-1)条有向边（即弧）的有向图。
无向完全图,恰有 条无向边的无向图。
稀疏图,图中边或弧的数目 e<<n2。
稠密图,图中边或弧的数目 e≈n2（准确地说，无向图的 e 接近于,有向图的 e接近于 n(n-1)。
)1(210 nne
)1(21?nn
)1(21?nn
图的术语
V1 V2
V3 V
4
V1 V2
V4 V5
V3
第七章 图第 11页子图,设有两个图 G=(V,E)和 G`=(V`,E`)，如果 V` V,E` E,
则称 G`为 G的子图 。
邻接点,若无向边 (v,v`)∈ E，则称顶点 v和 v`互为邻接点。
关联,称无向边 (v,v`)与顶点 v和 v`相关联。
顶点 V的度,与 v相关联的边的数目，记为 TD(v)。
顶点 V的入度,有向图中，以顶点 V为弧头（即终端点）的弧的数目，记为 ID(V)。
顶点 V的出度,有向图中，以顶点 V为弧尾（即初始点）的弧的数目，记为 OD(V)。
示例 2 有向图 G1,顶点数目 n=4；有向边或弧的数目 e=4； ID(V1)=1,OD(V1)=2,TD(V1)=3。
无向图 G2,顶点数目 n=5；无向边的数目 e=6； TD(V1)=2。
注,一个有 n个顶点，
e条边或弧的图，有：
).(21
1
n
i
iVTDe
图的术语
V1 V2
V3 V4
G1
V1 V2
V4 V5V3
G2
第七章 图第 12页路径,图 G中由顶点 V到 V`的路径是一个顶点序列
V=Vi0,Vi1,···,Vim=V`，其中 (Vij-1,Vij)∈ E,1≤j≤m。若图 G是个有向图
，则由顶点 V到 V`的路径亦是有向的，它由 E(G)中的有向边
<Vij-1,Vij>∈ E,1≤j≤m组成。
路径的长度,图 G中由顶点 V到 V`的路径长度是指在该路径上的边或弧的数目。
简单路径,若图 G中由顶点 V到 V`的一条路径上，除了 V和 V`
可以相同外，其余顶点均不相同，则称此路径为一条简单路径。
简单回路,起点 V和终点 V`相同的简单路径。亦称简单环。
回路或环,起点 V和终点 V`相同的路径。其余顶点允许重复出现。
示例 3 下述有向图 G3和无向图 G4
G3,顶点序列 V1,V2,V1是一个长度为 2的有向简单环； V1,V2,V3是由顶点 V1到 V3的长度为 2
的有向简单路径
G4,V1,V2,V3,V4是由 V1到 V4长度为 3简单路径
V1
V2 V3
V4
V1
V2
V3
G3 G4
第七章 图第 13页有根图,在一个有向图中，若存在一个顶点 V，从该顶点有路径可以到达图中其他所有顶点，则称此有向图为有根图，顶点 V称作该图的根。
连通,在无向图 G中，如果从顶点 V到顶点 V`有路径，则称 V和
V`是连通的。
连通图,若在无向图 G中,V(G)的任意两个不同的顶点 Vi和 Vj
都连通（即有路径），则称 G为连通图。
连通分量,无向图 G的极大连通子图称为 G的连通分量。显然
，任何连通图的连通分量只有一个，即是其自身。而非连通的无向图却有多个连通分量。
强连通图,在有向图 G中，若对于 V(G)中任意两个不同的的顶点 Vi和 Vj，都存在从 Vi到 Vj和从 Vj到 Vi的路径,则称 G是强连通图。
强连通分量,有向图 G的极大强连通子图称为 G的强连通分量
图的术语第七章 图第 14页强连通只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。
示例 5 设有下列图
V1
V2 V3
V4
V1
V2
V3
V1
V2 V3
V4 V6V5 V7
V1
V2 V3
V4
V5
V6 V7
V8有向图 G3 无向图 G4 无向图 G5
无向图 G6
则 G4与 G5均是连通图。
G6是非连通图，但它有两个连通分量 H1和 H2。
G3不是强连通图，因为 V3到 V2没有路径。但 G3有两个强连通分量，如下所示 V1
V2
V3
网,若将图的每条 边或弧 都赋上一个权，则将 这种带权的图称为网络，或简称网。 通常权是具有某种意义的数，比如它们可以表示两个结点之间的距离、耗费、流量等。
图的术语第七章 图第 15页示例 4 有关图的术语图解示例
0
1 3
2
4
4 1
1
2
3 7
⑴ 一个图 ⑵ 一个有向图
⑶ 一个有向标号图，且边上标有权。
简单路径：顶点 0→ 顶点 1 → 顶点 3 → 顶点 2。
非简单路径：顶点 0→ 顶点 1 → 顶点 3 → 顶点 2 → 顶点 4 → 顶点 1。
简单回路：顶点 1 → 顶点 3 → 顶点 2 → 顶点 4 → 顶点 1。
（ 1）
图的术语
（ 2） （ 3）
第七章 图第 16页示例 6 如下是一个网生成树,一个 连通图 G的子图如果是 一棵包含 G的所有顶点的极小连通子图，则该子图称为 G的生成树。 所谓极小是指边数最少。由于 n个顶点的连通图至少有 n-1条边，而所有包含 n-1边及 n个顶点的连通图都是无回路的树，所以生成树是无回路的树。若在生成树中去掉任何一条边，都会使之变为非连通图。若在生成树上任意添加一条边，就必定出现回路。
V1
V3
V2
V4
V5
11
10
3
2
8
65 4
图的术语第七章 图第 17页示例 7 设有如下无向图 G
1 2A
13
3 54
B
L M
C D E
12
6 87
F G H
9 1110
I J K
图 7.3 无向图及其连通分量则
(1) 无向图 G是一个非连通图
(2) 无向图 G有三个连通分量，分别为
A B
L M
C
F
J
D E
I K
G H
(3) 图 7.5是无向图 G中大连通分量的一棵生成树 A B
L M
C
F
J
图 7.5注,一棵有 n个顶点的生成树有且仅有 n-1条边，但是有 n-1
条边的图不一定是生成树。
图的术语第七章 图第 18页有向树,如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。
生成森林,一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
示例 8 如下表示一个有向图及其生成森林
A
F E
B
D
C
F
A
B
E
D
C
图 7.6 一个有向图及其生成森林
图的术语第七章 图第 19页
(1) LocVertex(G,v) 顶点定位函数确定顶点 v在图 G中的位置。若图中无此顶点，则返回函数值 0。
(2) Get Vertex(G,i) 取顶点函数求图 G中第 i个顶点。若 i大于图 G中的顶点数，则返回函数值 NULL。
(3) FirstADJ(G,v) 求第一个邻接点函数求图 G中顶点 v的第 1个邻接点。若 v没有邻接点或图 G中无顶点 v,则返回函数值 0。
(4) NextADJ(G,v,w) 求下一邻接点函数已知 w为图 G中顶点 v的某个邻接点，求顶点 w的下一个邻接点。若 w是 v的最后一个邻接点，则返回函数值 0。
(5) InsVertex (G,u)插入顶点操作和图 G中增添一个顶点 u为图 G的第 n+1个顶点，其中 n为插入之前图 G中所含顶点的个数。
图的基本操作第七章 图第 20页
(6) InsARC(G,v,w) 插入弧的操作在图 G中增添一条从顶点 v到顶点 w的弧。
(7) DelVertex(G,v) 删除顶点操作在图 G中删除顶点 v以及所有与顶点 v相关联的弧。
(8) DelARC(G,v,w) 删除弧的操作在图 G中删去一条从顶点 v到顶点 w的弧。
以上有关图的若干基本操作，前四种不涉及图的修改，后四种涉及图的修改。在后面讨论图的存储结构及图的操作中，主要考虑图的前四种基本操作。
图的基本操作第七章 图第 21页图的存储表示方法方法很多。对应于不同的应用问题，
往往选用不同的图的存储结构。具体选择哪一种表示法，主要取决于具体的应用场合以及欲施加的操作。
介绍一般情况下常用的图的有关存储结构。它们是数组表示法 —— 邻接矩阵邻接表表示法 —— 图的一种链式存储结构十字链表表示法 —— 有向图的另一种链式存储结构邻接多重表表示法 —— 无向图的另一种链式存储结构
图的存储结构第七章 图第 22页数组表示法 —— 邻接矩阵邻接矩阵 （ Adjacency Matrix）是表示图中顶点之间相邻关系的矩阵。
设 G=(V,E)是具有 n个顶点的图，则 G的邻接矩阵是具有如下性质的 n阶方阵
中的边不是或若 中的边是或若 )(,),(,0 )(,),(,1,GEvjvivjvi GEvjvivjvijiA
示例 9 设有向图 G1和无向图
G2为
V1 V2
V3 V4
V1 V2
V4 V5
V3
则它们的邻接矩阵 A1和 A2分别为有向图 G1 无向图 G2
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 0 0
A1= A2=
图的存储结构 – 邻接矩阵第七章 图第 23页说明
(1) 无向图的邻接矩阵是对称的，有向图则不一定；
(2) 设图 G共有 n个顶点，则若 G是有向图，则存储空间为 n2位，
而若 G是无向图，则存储空间可为 n(n+1)/2位，即仅存储上（或下）
三角元素；
(3) 无向图顶点 Vi的度是邻接矩阵中第 i行（或第 i列）的元素之和，
即而有向图顶点 Vi的出度为邻接矩阵中第 i行元素之和，入度为第 i列元素之和，即示例 10 对于下述之无向图 G7和有向图 G8
V1 V4
V2 V3
V1 V2
V5 V4
记其相应邻接矩阵分别为 A7和 A8，则有无向图 G7 有向图 G8
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
1 0 0 0 0
0 0 0 1 0
A7= A8=
V3
)],[(];,[)(
11
n
j
n
ji
ijAorjiAVTD
n
j
n
j
ii ijAVIDjiAVOD
1 1
],[)(],,[)(
第七章 图第 24页
(4) 欲检测在图 G中总共有多少条边，必须按行、列逐次检测邻接矩阵的各元素，故最坏情况下需时 O(n2)。
若 G是网，则邻接矩阵可定义为
否则或或若
0
);(,),(,],[ GEVVVVwjiA jijiij
其中 wij表示边上的权值,∞表示一个计算机允许的、大于所有边上权值的数。
示例 11 下面给出一个网及其邻接矩阵
V1 V2
V5
V3 V4
3
8
6
5 4
2
11
10
∞ 3 5 8 ∞
3 ∞ 6 4 11
5 6 ∞ 2 ∞
8 4 2 ∞ 10
∞ 11 ∞ 10 ∞
A=
无向网示例 12 有向网及其邻接矩阵（图 7.9）
3
5
48
7 9
61
5
5
V4
V3
V2V1
V6
V5
∞ 5 ∞ 7 ∞ ∞
∞ ∞ 4 ∞ ∞ ∞
8 ∞ ∞ ∞ ∞ 9
∞ ∞ 5 ∞ ∞ 6
∞ ∞ ∞ 5 ∞ ∞
3 ∞ ∞ ∞ 1 ∞
A=
图 7.9
第七章 图第 25页下面给出建立无向网的存储结构即邻接矩阵的算法。
数据结构
#define MAX_VERTEX 20 //最大顶点个数
typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网
typedef struct ArcCell{
VRType adj; //顶点关系类型，无权图用 0,1表示相邻否，带权图为权
InfoType *info; //相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX+1][MAX_VERTEX+1];
typedef struct{
VertexType vexs[MAX_VERTEX+1]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //顶点数，弧数
GraphicKind kind; //图的类型
} Mgraph;
图的存储结构 – 邻接矩阵数组表示法 —— 邻接矩阵第七章 图第 26页算法描述
Status CreateGraph( Mgraph &G )
{ //建立无向网的数组型存储结构
for( i=1; i <= G.vexnum; i++ )
scanf( &G.vexs[i] ); //输入 n个顶点的信息
for( i=1; i <= G.vexnum; i++ )
for( j=1; j <= G.vexnum; j++ )
G.arcs[i][j] = ( ∞,NULL ); //初始化
for( k=1; k < G.arcnum; k++ )
{ scanf( &v1,&v2,&w); //输入一条边的信息,w为与边相关的权
i = LocVertex( G,v1 );
j = LocVertex( G,v2 ); //确定 v1,v2在 G中的位置
G.arcs[i][j].adj = w;
G.arcs[j][i].adj = w //假设无其它和边相关的信息
}
} //CreateGraph 算 法 7.1
注,时间复杂度为 O(n2+e·n).
图的存储结构 – 邻接矩阵第七章 图第 27页说明可在前述数组型存储结构下实现诸如 FirstADJ
(G,v)的基本操作。
先由 LocVertex(G,v)找到顶点 v在 G中的位置，即 v
在一维数组 vexs中的序号 i，则二维数组 Arcs中第 i行上第一个 adj域的值为 1的分量所在列号 j，便为所求顶点 v
的第一个邻接点在图 G中的位置。
同理，求 NextADJ(G,v)便为 j列之后第一个 adj域的值为 1的分量所在列号。
图的存储结构 – 邻接矩阵第七章 图第 28页邻接表 (Adjacency List)表示法类似于树的孩子链表表示法。它是图的一种链式存储结构。
对于图 G中的每个顶点 Vi，该方法把所有邻接于 Vi的顶点链成一个单链表，这个单链表就称为该顶点 Vi的邻接表。
结点形式
(1) 边或弧的结点
adjvex：邻接域，指示与顶点 Vi邻接的点在图中的位置
nextarc：链域，指示下一条边或弧的结点
info：数据域，存储和边或弧相关的信息
(2) 顶点结点
vexdata：数据域，存储顶点 Vi的名或其他有关信息
firstarc：链域，指向链表中第一个结点，这些顶点结点通 常以顺序结构（向量）的形式存储，以便随机地访问任一顶点的链表。
adjvex nextarc info
vexdata firstarc
邻接表表示法第七章 图第 29页
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
邻接表表示法
V1 V2
V4 V5
V3
无向图 G2
对无向图 G2,若输入序对分别为 1,2; 1,4; 2,3; 2,5;3,4; 3,5；可得示例：
第七章 图第 30页下面给出建立无向图的邻接表表示存储结构的算法。
数据结构
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex; //顶点的位置
struct ArcNode *nextarc; //下一个顶点的指针
InfoType *info; //其它信息
}ArcNode;
typedef struct VNode{
VertexType data; //数据
ArcNode *firstarc; //指向相邻顶点的链表
}VNode,AdjList[MAX_VERTEX_NUM+1];
typedef struct{
AdjList vertices; //顶点向量
int vexnum,arcnum;
int kind;
}ALGraph;
邻接表表示法第七章 图第 31页算法描述
Create_adjlist( ALGraph &ga,int n,int e )
//建立无向图的邻接表
{ for( i=1; i<=n; i++ )
{ scanf(ga.vertices[i].data);
ga.vertices[i].firstarc = NULL; ga.vexnum = n }
for( k=1; k <= e; k++ )
{ scanf(i,j); //读入边 (vi,vj)的顶点对序号
s = new(ArcNode); //生成邻接点序号为 j的边表结点 s
s->adjvex = j; s->nextarc=ga.vertices[i].firstarc;
ga.vertices[i].firstedge = s; //插表头
s = new(ArcNode); //生成邻接点序号为 i的边表结点 s
s->adjvex = i;
s->nextarc=ga.vertices[j].firstarc;
ga.vertices[j].firstarc = s; //插表头
}
ga.arcnum = e;
} //Create_adjlist
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
邻接表表示法
V1 V2
V4 V5
V3
无向图 G2对无向图 G2,若输入序对分别为 1,2; 1,4; 2,3; 2,5;3,4; 3,5；可得第七章 图第 32页说明
(1) 邻接表中顶点结点是有序的,以向量存储 ；
(2) 无向图 的邻接表，第 i个结点的度为第 i个链表的结点数；而在有向图中，第 i个链表的结点数仅是顶点 Vi的出度。为求入度，必须遍历整个表。在所有链表中其邻接点域的值为 i的结点的个数是顶点 Vi的入度；
(3) 如需确定顶点的入度，可建立一个有向图的逆邻接表
，即对每个顶点 Vi建立一个邻接以 Vi为头的弧的表；
(4) 称无向图的邻接表为 边表 ；称有向图的邻接表为 出边表 ；称有向图的逆邻接表为 入边表 ；
邻接表表示法
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
第七章 图第 33页说明邻接表表示法
(5) 对于一个具有 n个顶点 e条边的图 G，若 G是无向图，则它的邻接表表示中有 n个顶点表结点和 2e个边表结点；若 G是有向图，则它的邻接表表示或逆邻 接表表示中均有 n个顶点表结点和 e个边表结点；
(6) 邻接矩阵与顶点数 n有关，故在边数很多即
e<<n2时，宜采用邻接表表示法。
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
第七章 图第 34页十字链表 (Orthogonal List) 是有向图的另一种链式存储结构。
用十字链表存储 有向图,实际上就是将有向图的邻接表和逆邻接表结合起来得到的一种链表。
十字链表中的结点形式
(1) 弧结点 <Vi,Vj>
tailvex：尾域，指示弧尾顶点 Vi在图中的位置
headvex：头域，指示弧头顶点 Vj在图中的位置
hlink：链域，指向以 Vj为弧头的下一条弧
tlink：链域，指向以 Vi为弧尾的下一条弧弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。
(2) 顶点结点 Vi
data：数据域，存储和顶点相 关的信息
firstin：链域，指向以 Vi为弧头的第一个弧结点
firstout：链域，指向以 Vi为弧尾的第一个弧结点
tailvex headvex hlink tlink
data firstin firstout
十字链表表示法第七章 图第 35页
#define MAX_VERTEX_NUM 20
typedef struct ArBox{
int tailvex,headvex;
struct ArBox *hlink,*tlink;
}ArcBox;
typedef struct VexNode{
VertexType data;
ArcBox *firstin,*firstout;
}VexNode;
typedef struct{
VexNode xList[MAX_VERTEX_NUM];
int vernum,arcnum;
}OLGraph;
十字链表表示法
V1 V2
V3 V4
V1 1 2 1 3 ∧
V2 ∧
V3 3 1 3 4 ∧
V4 4 1 4 2 4 3 ∧∧∧
∧
∧
1
2
3
4
图 7.11 有向图的十字链表示例 13,一有向图及其对应的十字链表第七章 图第 36页算法描述
Status Create_ortho( OLGraph &G)
{ //建立有向图的十字链表存储结构
scanf( &G.vexnum,&G.arcnum ); //输入顶点和弧的数目
for( i = 1; i <= G.vexnum; i++ )
{ scanf(G.xlist[i].data); //输入顶点信息
G.xlist[i].firstin=NULL;
G.xlist[i].firstout=NULL //指针初始化
};
for( k = 1; k <= G.arcnum; k++ )
{ scanf( &vt,&vh ); //输入弧的信息
i=LocVertex(G,vt); j=LocVertex(G,vh);
//确定弧尾和弧头在图中的位置
p = new(ArcBox); p->tailvex = i; p->headvex = j;
p->hlink = G.xlist[j].firstin;
G.xlist[j].firstin = p;
p->tlink = G.xlist[i].firstout;
G.xlist[i].firstout = p;
//将弧结点分别插入在两个链表中
}
} //Create_ortho 算 法 7.2
十字链表表示法第七章 图第 37页邻接多重表（ Adjacency Multilist）是 无向图 的另一种 链 式存储结构。
在无向图的邻接表表示法中，每条边 (Vi,Vj)是用两个结点表示的，分别在第 i个和第 j个链表中。这给图的某些操作（如检测某条边是否被访问即搜索过、删去一条边等）带来不便。
此时，若采用 邻接多重表表示法 则更为方面适宜。
邻接多重表的结点形式
(1) 边结点
mark：标志域，用以标记该条边是否被搜索过
ivex,jvex：该边依附的两个顶点在图中的位置
ilink,jlink：链域，分别指向下一条依附于顶点 ivex,jvex的边
(2) 顶点结点
data：数据域，存储和该顶点相关的信息
firstedge：链域，指示第一条依附于该顶点 Vi的边
mark ivex ilink jvex jlink
data firstedge
邻接多重表表示法第七章 图第 38页
#define MAX_VERTEX_NUM 20
typedef enum{unvisited,visited} VisitIF;
typedef struct Ebox{
VisitIF mark;
int ivex,jvex;
struct Ebox *ilink,*jlink;
InfoType *info;
}Ebox;
typedef struct VexBox{
VertexType data;
Ebox *firstedge;
}VexBox;
typedef struct{
VexBox adjmulist[MAX_VEXTEX_NUM];
int vexnum,edgenum;
}AMLGraph;
V1 V2
V4 V5
V3
无向图 G2
注,表示法不唯一邻接多重表表示法
V1
V2
V3
V4
V5
1 2 1 ∧ 4
3 2 3 4
5 2 3 5
∧
∧ ∧∧
1
2
3
4
5
图 7.12 无向图 G2
的邻接多重表第七章 图第 39页图的遍历（ graph traversal）,从图的某一顶点出发，沿着某条搜索路径，对图中所有顶点各作一次访问。
连接图的遍历,从图中任一顶点出发，顺着边可访问到该图中所有的顶点。
非连通图的遍历,需多次调用搜索过程。
遍历图较遍历树的复杂性,为了避免重复访问同一顶点，
必须记住每个顶点是否曾被访问过。
两种常用的遍历图的方法,深度优先 搜索遍历和 广度优先搜索遍历。它们对无向图和有向图均适用。
图的遍历算法,它是求解图的连通性问题、拓扑排序和求关健路径等算法的基础。
图的遍历第七章 图第 40页图的深度优先搜索 （ Depth-first search，简记为 DFS）遍历是 树的先根遍历的推广 。
算法思想,设给定图 G的初始状态是所有顶点均未曾被访问。
(1)以图 G中某一顶点 V0为初始出发点，首先访问该出发点 V0，
并将其标记为已访问的,(2)选取与 V0邻接的未被访问的任一顶点 W
访问之并作标记,(3)再选取与 W邻接的未被访问的任一顶点访问之并作标记，依次类推，重复上述访问。
当即达到一个顶点时，则又从最后被访问的且尚有邻接顶点未被访问过的顶点，重复上述搜索过程，直到所有的被访问顶点的邻接顶点都被访问过为止。
显然，上述搜索过程是 递归定义 的，其搜索次序体现了优先向纵深发展 的趋势，故此搜索法被称之为 浓度优先搜索法 。
深度优先搜索（ DFS）遍历第七章 图第 41页示例 1 无向图 G4及其浓度优先搜索的过程
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
1 5 1
7V6
V7
3
V4
2 V
8
4 V
5
2 8
(a) 无向图 G4
图 7.3 遍历图的过程
(b) 深度优先搜索的过程所得的顶点访问序列为
V1→ V 2→ V 4→ V 8→ V 5→ V 3→ V 6→V 7
深度优先搜索（ DFS）遍历第七章 图第 42页图的深度优先搜索遍历算法
void DFSTraver( Graph g )
{ //对图 g按深度优先进行遍历
for( vi=1; vi <= vexnum; vi++ )
visited[vi]=false; //标志数组初始化
for( vi=1; vi <= vexnum; vi++ )
if(!visited[vi]) dfs(g,vi) //调用从 vi出发遍历的递归过程
} //DFSTraver 算法 7.3
void dfs( Graph g,int v )
{ //从 vo出发深度优先遍历图 g
visite(v); //printf(v)
visited[v]=true;
for( w=FirstAdj(g,v); w; w=NextAdj(g,v)) //w为 vo的邻接点
if( !visited[w]) dfs(g,w);
} //dfs 算法 7.4
第七章 图第 43页算法分析
(1) 为了在遍历过程中便于区分顶点是否曾被访问过，特附设一个 访问标志数组 visited，其初值均为 false，一旦某个顶点被访问，则其相应的分量被置为 true；
(2) 显然，过程 dfs是一个 递归过程 。但在遍历图时，对图中每一个未被访问过的顶点，仅调用一次 dfs过程，因为一旦它被访问过并作了标志，则不再从它出发进行搜索。因此，
遍历图的过程实际上是结每个顶点查找其邻接点的过程 ；
(3) 算法的时间复杂度取决于所采用的 存储结构 。在每次递归调用时，除了访问顶点及做标记外，主要的时间耗费在从该顶点出发搜索它的所有邻接点。
深度优先搜索（ DFS）遍历
图的遍历第七章 图第 44页用邻接矩阵表示图,dfs算法的时间复杂度是 O(n2)。这是因为搜索一个顶点的所有邻接点需花费 O(n)时间来检查矩阵相应行中所有的 n个元素，故从 n个顶点出发搜索所需时间是 O(n2)。
用邻接表表示图,搜索 n个顶点的所有邻接即为对各边表结点扫描一遍，故 dfs算法的时间复杂度为 O(n+e)，这里 n为图中顶点数
,e为无向图中边的数目或有向图中弧的数目；
(4) 算法的空间复杂度：所需用的辅助空间是标志数组和实现递归所用的栈。故它们的空间复杂度为 O(n)；
(5) 对于用邻接矩阵或邻接表作为存储结构时，其具体的 dfs算法，与采用的数据结构及存储结构有关，可在算法 7.4的基础上改造之；
(6) 若 G是 连通图,则从初始出发点开始的搜索过程结束也就意味着完成了对图 G的遍历。而若 G是 非连通图,则从图中任一顶点出发进行深度优先搜索不能访问到图中所有顶点。若从每个连通分量中都能先取一个顶点作为出发点进行搜索，便可访问到整个非连通所有顶点。（类似与森林的遍历）
算法分析第七章 图第 45页图的广度优先搜索（ Breadth-First search，简记为 BFS），它的遍历 类似于树的按层次遍历 。
算法思想,设给定图 G的初始状态是所有顶点均未曾被访问过
。 (1)在 G中任选一顶点 V0为初始出发点，则首先访问该出发点 V0，
并将其标记为已访问过,(2)接着依次访问 v0的所有邻接点
w1,w2,···,wt，然后,(3)再依次访问与 w1,w2,··,wt邻接的所有未曾访问过（每次访问某顶点，均作了标记）的顶点，依次类推，直至图中所有和初始出发点 v0有路径相通的顶点都已访问到为此。
若此时图中尚有未被访问的顶点 （在另一个连通子图中）,则选中这个未被访问的顶点，重复上述过程，直到图中所有顶点都被访问为止。
此算法的搜索次序体现了 优先朝横向发展 的趋势，故此搜索法被称之为广度优先搜索法。
广度优先搜索（ BFS）遍历
图的遍历第七章 图第 46页示例 4 无向图 G4及其广度优先搜索的过程
(a) 无向图 G4
图 7.13 遍历图的过程
(c) 广度优先搜索的过程所得的顶点访问序列为
V1→ V 2→ V 3→ V 4→ V 5→ V 6→V 7 →V 8
广度优先搜索（ BFS）遍历
图的遍历
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
1
V61 V7
73 6
V4 V5
V8 8
5
2 2
3
4
第七章 图第 47页在遍历过程中也需要一个访问标志数组。此外，为了顺次访问路径长度为 2,3,···的顶点，还需附设一个 队列 以存储已被访问的路径长度为 1,2,···的顶点。
void BFSTraver(Graph g,int visited[])
{ //对图 g按广度优先进行遍历
for( vi=1; vi <= vexnum; vi++ )
visited[vi] = false; //标志数组初始化
for( vi=1; vi <= vexnum; vi++ )
if( !visited[vi] )
bfs(g,vi) //调用从 vi出发广度优先遍历的递归过程
} //traver
算法 7.3
广度优先搜索（ BFS）遍历第七章 图第 48页
void bfs(Graph g,int v0 )
{ //从 vo出发广度优先遍历图 g
visite( v0 );
visited[v0] = true;
InitQueue( Q ); //初始化设置空队列 Q
EnQueue( Q,v0 ); //v0进队列 Q
while( !Empty( Q ))
{ v = DlQueue(Q); //队头元素 v出队列
w = FirstADJ(g,v); //求 v的邻接点
while( w≠0 )
{ if( !visited[w])
{ visite[w]; visited[w] = true;
EnQueue( Q,w )
};
w = NextADJ(g,v,w) //求下一邻接点
}
}
} //bfs 算法 7.5
时间复杂度与 dfs算法相同。区别仅在于对顶点，访问的顺序不同。
广度优先搜索（ BFS）遍历第七章 图第 49页对于无向图 G的遍历而言，
(1)若 G是 连通图,则从 G中任一顶点出发，仅需一次调用搜索过程（ dfs或 bfs），便可访问图中各个顶点
。
(2)若 G是 非连通图,则从 G中任一顶点出发，只能访问到初始出发点所在的连通分量中的所有顶点。
(3)若从每个连通分量中都选一个顶点作为初始出发点进行搜索，便可访问到整个非连通图，非连通图的遍历必须多次调用 dfs或 bfs算法。每次调用所得到的顶点访问序列恰为各个连通分量中的顶点集。
无向图的连通分量
图和连通性问题第七章 图第 50页示例 5 给定如下之无向图
G3及其邻接表
A B
L M
A
B
C
D
E
F
G
H
I
J
K
L
M
12 6 3 2 ∧
13 1 ∧
1 ∧
5 ∧
4 ∧
1 ∧
11 9 8 ∧
12 10 2 ∧
13 10 1 ∧
11 7 ∧
7 ∧
13 12 ∧
8 7 ∧
1
2
3
4
5
6
7
8
9
10
11
12
13
C D E
F G H
I J K
1 2
12 13
3 4 5
6 7 8
9 10 11
图 7.3 无向图 G3
图 7.14 G3的邻接表无向图的连通分量第七章 图第 51页对于如图 7.3所示的非连通无向图 G3，按照图 7.14所示 G3
的邻接表进行深度优先搜索遍历，分别从顶点 A,D和 G出发，
三次调用 dfs过程，可得到如下之顶点访问序列
ALMJBFC,DE,GKHI
由这三个顶点集分别加上所有依附于这些顶点的边，便构成了非连通无向图 G3的三个连通分量
A B
L M
C
F
J
D E
G H
I K
求非连通的连通分量的算法与 traver算法几乎完全一样，
只需在 dfs(g,vi)后增加 print过程，打印出有关顶点和边的信息
。
无向图的连通分量第七章 图第 52页在图论中，常常将树定义为一个 无回路连通图 。例如，下述两个图就是无回路连通图初看之下它们时不是树，但只要选定某个顶点做根，以树根为起点对每条边定向，就能将它们变为通常的树。
设 G=(V,E)是一个具有 n个顶点的连通图，则从 G中任一顶点出发作一次深度或广度优先搜索遍历图时，必将 E(G)分成两个集合
T(G)和 B(G),这里 T(G)是遍历该图时所通过的边集，则 B(G)是剩余的边集。今考虑图 G`=(V,T)。 由于 V(G`)=V(G),E(G`)=T<=E(G)
，则 G`是 G的子图，且形成包括 G所有顶点的一棵树,G`中的边构成该树的枝,称此树为 G的生成树 。
生成树
生成树第七章 图第 53页定义 1,一个连通图 G的子图如果是一棵包括 G的 所有顶点的树,则称该子图为 G的生成树（
Spanning Tree）。
推论,由于 n个顶点的连通图至少有 n-1条边，而所有包含 n-1条边及 n个顶点的连通图都是无回路的树,所以生成树是连通图的极小连通子图。
定义 2,由 dfs遍历所得到的生成树称为深度优先生成树；由 bfs遍历所得到的生成树称为广度优先生成树。
生成树
生成树第七章 图第 54页示例 6 无向连通图 G4
V1
V2 V3
V4 V5 V6 V7
V8
的深度优先生成树和广度优先生成树
G4的广度优先生成树注,虚线表示集合 B(G)中的边
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
V4
V8
V5
V6
V7
G4的深度优先生成树生成树第七章 图第 55页上面给出的生成树定义，是从连通图的观点出发，针对无向图而言的。由于从图的遍历可求得生成树,因此亦可从另一角度来定义生成 树 。
定义 3,若从图的某顶点出发，可以系统地访问遍图中的所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。
此定义不仅适用于无向图，对有向图同样适用
。显然，若 G是强连通的有向图，则从其中任一顶点 v出发，都可以访问遍 G中的所有顶点，从而得到以 v为根的生成树。若 G是有根的有向图，设根为 v
，则从根 v出发也可完成对 G的遍历，因此也能得到
G的以 v为根的生成树。
生成树第七章 图第 56页示例 7 有根的有向图及其 dfs生成树与 bfs生成树
V1
V2 V6
V4
V3
bfs生成树
V1
V2 V6
V3
V1
V2 V5
V3 V7
dfs生成树
V5
V7
V4
V6
V4 V5
V7
生成树第七章 图第 57页图的生成树 不是唯一 的，从不同的顶点出发进行遍历，可以得到不同的生成树。
对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。
示例 6 无向图 G3及其深度优先生成森林
A B
L M
C D E
F G H
I J K
图 7.3 无向图 G3
A
L
J B
M
F C
D
E K
H
I
G
1
2 6 7
3
4 5
8
9
10
11 13
12
注,虚线为集合 B(G)中的边
G3的深度优先生成森林生成树第七章 图第 58页下面给出非连通图的深度优先生成森林的算法,设以孩子兄弟链表 作为生成森林的存储结构。
void dfs_forest(Graph g,Tree &root )
{ /*建立非连通图的深度优先森林的孩子兄弟链表,root为指向根结点的指针
，局部变量 q指向最后生成的结点 */
root = NULL; //初始化建空树
for( vi=1; vi <= vexnum; vi++ ) visited[vi]=false;
for( vi=1; vi <= vexnum; vi++ )
if( !visited[vi] )
{ p = new(TreeNode); p->data = vi;
p->fch = NULL; p->nsib = NULL; //建生成树的根结点
if( root == NULL ) root = p; //第一棵树的根
else q->nsib = p; //其他树的根
q = p;
dfs_tree(g,vi,p) //建以 p为根的生成树
}
} //dfs_forest 算 法 7.6
生成树第七章 图第 59页
void dfs_tree(Graph g,int vo,Tree &p )
{ /*从 vo出发深度优先搜索图 g，建以 p↑为根的生成树的孩子兄弟链表，局部变量 q指向最后生成的结点，局部变量 false*/
visited[vo]=true;
w = FirstADJ(g,vo); first=true; //w为图 g中 vo的第一个邻接点
while( w≠0 )
{if( !visited[w] )
{ if( first ) //把 第一个邻接点作为长子
{ p->fch = new(TreeNode); q=p->fch; first=false }
else
{ q->nsib = new(TreeNode);
q = q->nsib; //建生成树的一条边
}
q->data = w; q->fch = NULL; q->nsib = NULL;
dfs_tree(g,w,q); //从 w出发深度优先搜索图 g，
建以 q为根的生成树
}
w = NextADJ (g,vo,w);
} //while
} //dfs_tree 算 法 7.7
生成树第七章 图第 60页对于网络 G=(V,E)，边是带权的,因而 G的生成树的各边也是带权的。
定义 4,称由网 G=(V,E)所产生的生成树各边的权值总和为该生成树的权，并称权最小的生成树为网 G的最小生成树（
Minimum Spanning Tree）。
生成树和最小生成树有许多重要的应用。令图 G的顶点表示城市，边表示连接两个城市之间的通信线路。 n个城市之间最多可设立的线路共有 n(n-1)/2条，而把 n个城市连接起来至少要有 n-1条线路。因此，图的生成树表示了建立通信网的可行方案。
假设给图中的边都赋予权，而这些权可表示两上城市之间的通信线路的长度或建造代价。
最小生成树
最小生成树第七章 图第 61页构造连通网的最小（代价）生成树 (minumum-cost
spanning tree或 MST)的两个算法,普里姆（ Prim） 算法 和 克鲁斯卡尔 Kruskal算法 。
给定一个连通无向图 G,且它的每条边均有相应的长度或权值，则 MST是一个包括 G的所有顶点及其边子集的图,边的子集满足下列 条件,
(1) 这个子集中所有边的权之和为所有 边子集 中最小的 ；
(2) 子集中的边能够保证图是 连通 。
最小生成树
最小生成树第七章 图第 62页示例 8 一个图及其 MST。
● 所有的线都是原图的边,MST中边的子集用粗线（兰色）表示
●如果用边（ D,F）代替边（ C，
F），可得到另一个 MST。
A
B
E
F
C
D
7 5
2 69
1
1
2
最小生成树
MST的性质,假设 N=（ V,{E}） 是一个连通图,U是 V的非空子集。
若?e=(x,y)，其权重最小，且 x ∈ U,y∈ V-U
则一定存在一棵包含边 e的最小生成树。
第七章 图第 63页
Prim 算法利用 MST 性质来构造连通网的最小生成树。它 着眼于顶点的处理 。
算法思想：设 N=(V,E)是连通网。为简化用序号 1
至 n来表示顶点集合，则 V={1,2,··,n}。设所求的最小生成树为 T=(V,TE)，其中 V是 T的顶点集,TE是 T的边集。将 N中边上的权看作是长度。 Prim 算法思想的执行步骤如下：
(1)初始化：令 U={u0} (u0∈ V),TE=? ;
(2)在所有 x∈ U,y∈ V-U的边 (x,y) ∈ E中找一条代价最小的边 (x0,y0)并入集合 TE,同时 y0并入 U；
(3) 重复 (2)，直至 U=V时为止。
此时 TE中必有 n-1条边，且 T=(V,TE)为 N的最小生成树 。
构造最小生成 树的 Prim 算法第七章 图第 64页示例 9 设有如下之连通网 N1
今欲使用 Prim算法构造连通网 N1的最小生树。
1
3
2 4
5 6
56
5
3 6 4 2
6
51
其权重矩阵为
∞ 6 1 5 ∞ ∞
6 ∞ 5 ∞ 3 ∞
1 5 ∞ 5 6 4
5 ∞ 5 ∞ ∞ 2
∞ 3 6 ∞ ∞ 6
∞ ∞ 4 2 6 ∞
A=
构造最小生成 树的 Prim 算法
[分析 ] 先采用图示法，然后写出 Prim算法。
初始化 令 u0=1，即 u={1},
设置一辅助数组 Closedge[vtxptr],域 lowcost、域 vex
域 lowcost,记录每个顶点 v ∈ V-U，到 U集的最小代价域 vex,记录 该边在 U集中的顶点第七章 图第 65页
v
c l a se d g e
2 3 4 5 6 U V - U
v e x
l o w c o st
①
6
①
1
①
5
①
∞
①
∞
{ 1 } { 2,3,4,5,6 }
i = 1,k = 3
输出 1 3
v e x
l o w c o st
③
5 0
①
5
③
6
③
4
{ 1,3 } { 2,4,5,6 }
i = 2,k = 6
输出 3 6
v e x
l o w c o st
③
5 0
⑥
2
③
6 0
{ 1,3,6 } { 2,4,5 }
i = 3,k = 4
输出 6 4
v e x
l o w c o st
③
5 0 0
③
6 0
{ 1,3,6,4 } { 2,5 }
i = 4,k = 2
输出 3 2
v e x
l o w c o st 0 0 0
②
3 0
{ 1,3,6,4,2 } { 5 }
i = 5,k = 5
输出 2 5
v e x
l o w c o st 0 0 0 0 0
{ 1,3,6,4,2,5 }
图 7.17 构造最小生成树过程中辅助数组中各分量的值
∞ 6 1 5 ∞ ∞
6 ∞ 5 ∞ 3 ∞
1 5 ∞ 5 6 4
5 ∞ 5 ∞ ∞ 2
∞ 3 6 ∞ ∞ 6
∞ ∞ 4 2 6 ∞
A=
1
3
2 4
5 6
56
5
3 6 4 2
6
51
第七章 图第 66页
void MiniSpanTree_PRIM( Mgraph g,VertexType u )
{ //从 uo出发构造网 gn的最小生成树,按 Prim算法输出生成树上各条边
k = LocateVex( g,u );
for( j = 1; j <= g.vernum; j++ )
if( j!=k )closedge[j] = {u,g.arcs[k][j].adj}; //辅助数组初始化
closedge[k].lowcost = 0; //lowcost值为 0说明并入顶点集 U
for( v = 1; v < g.vexnum,v++ )
{ k = minimum(closedge); //lowcost值为 0的数组元素不参与取最小值运算
printf( closedge[k].adjvex,g.vex[k] ); //输出生成树的边
closedge[k].lowcost = 0; //顶点 k并入 U集
for( j = 1; j <= g.vexnum; j++ )
if( g.arcs[k][j].adj ＜ closedge[j].lowcost )
{ closedge[j].lowcost = { g.vexs[k],g.arcs[k][j].adj }
//在新的顶点并入 U之后，重新选择具有最小代价的边
}
} //minispantree_PRIM 算 法 7.8
Prim 算法算法分析：时间复杂度 O(n2)，其中 n为连通网 N的顶点数。
第七章 图第 67页构造最小生成树的 Kruskal 算法克鲁斯卡尔 (Kruskal) 算法亦是利用 MST性质来构造连通网的最小生成树，但它 着眼于边的处理 。
算法思想,按权值递增的顺序来构造最小生成树 。 设
N=(V,E)是连通网，而所求最小生成树为 T=(V,TE)，其中 V是顶点集,TE是 T的边集。将 N中边上的权看作是长度。 Kruskal算法的执行步骤如下：
(1) 初始化,令 T=(V,?)(即 TE=?)为只有 n个顶点而无边的非连通图，图中每个顶点自成一个连通分量；
(2) 在 E中选取一条代价最小的边 (u,v)，若该边依附的顶点 u,v落在
T中不同的连通分量上（使该边加入 T中后不能形成回路），则将此边加入到 TE中，并在 E中删除该边，否则舍去选择下一条边；
(3) 重复 (2)，直至 T中所有顶点都在同一连通分量上时为止。
第七章 图第 68页示例 10 设连通网 N1如示例 2，今按 Kruskal 算法思想用图示法构造出一棵最小生成树：
(1) 初始化,TE=? ；
1
3
2 4
5 6
56
5
3 6 4 2
6
51
1
3
2 4
5 6
构造最小生成树的 Kruskal 算法第七章 图第 69页
Kruskal 算法的粗略描述
void MiniSpanTree_KRUSKAL( )
{ TE =?;
while( TE中少于 n-1条边 )
{ 从 E(N)中选取一条具有最小权值的边 (v,w)；
从 E(N)中删去边 (v,w)；
if( 边 (v,w)加入到 T中不能形成回路 )
将边 (v,w)加入到 TE中 ;
}
} //minispantree_KRUSKAL
算法分析：时间复杂度 O(eloge)，其中 e为连通网 N的边数。
注,Kruskal 算法的时间复杂度仅与网中边数有关，而与顶点 数无关，故相对于 Prim算法而言，适合于求边稀疏的网的最小生成树。
构造最小生成树的 Kruskal 算法第七章 图第 70页示例 11 设有如下之连通网 N2
执行 Kruskal 算法的过程如下（简化形式）初始状态
1 2
5 4
6 3
16
18
21
33
11
14 619
6
5
1 2
5 4
6 3
构造最小生成树的 Kruskal 算法第七章 图第 71页定义,一个无环的有向图称做有向无环图 (Directed Acycline Graph),简称 DAG 图。
示例 12 比较下列树、图图 7.21 有向树,DAG 图和有向图（有环）一例
DAG 图是一类较有向树更一般的特殊有向图。它是描述含有公共
（共享）子式的表达式的有效工具，也是描述一个工程项目（
Project）是否能顺利进行以及估算整个工程项目完成所必须的最短时间等方面应用的有效工具。
有 向 无 环 图第七章 图第 72页示例 12 下述表达式
((a＋ b)× (b× (c＋ d))＋ (c＋ d)× e)× ((c＋ d)× e) (△ )
可分别用 二叉树 及 有向无环图 描述如下图 7.22 用二叉树描述表达式 (△ )
＋
a b
×
＋
b c d
＋ c d
＋
e×
＋
× e
×
c d
×
×
＋×
＋
a b
×
ec d× ＋ 图 7.23 描述表达式 (△ )的有向无环图
有 向 无 环 图第七章 图第 73页术语与概念定义 1 （ AOV-网） 若在有向图 G 中，用顶点表示活动或任务
，用弧（有向边）表示活动或任务间的优先关系，则称此有向图为顶点表示活动的网 （ Activity on vertex network），简称 AOV-网。
在 AOV-网 中，若从顶点 i 到顶点 j 有一条有向路径，则 i 是 j
的前驱,j 是 i 的后继。若 <i,j> 是网中一条弧，则 i 是 j 的直接前驱,j 是 i 的直接后继。
定义 2 （偏序与全序） 若集合 X 上的关系 R是自反的、反对称的和传递的，则称 R 是集合 X 上的偏序 (Partial Order)关系 ；
设 R 是集合 X 上的偏序，如果对 每个 x,y∈ X,必有 xRy 或 yRx，
则称 R 是集合 X 上的全序（ Full Order）关系。
拓 扑 排 序第七章 图第 74页示例 13 下述两个有向图图 7.25 表示偏序和全序的有向图图中弧 <x,y> 表示 x≤y。则 (a) 表示偏序,(b) 表示全序。偏序指集合 仅有部分成员之间可以比较,而 全序指集合中全体成员之间均可比较 。
定义 3 （拓扑排序） 由某个集合上的一个偏序得到该集合上的一个全序的操作称为拓扑排序（ Topological Sort）,
比如，在图 7.25(a) 中的有向图上增加一个表示 2≤3 的弧，则 (a) 表示的亦为全序，且称此全序为 拓扑有序 （ Topological Order），而由偏序定义得到拓扑有序的操作便是拓扑排序。
2
3
41 2 3 41
(b)(a)
拓 扑 排 序第七章 图第 75页拓扑排序的方法拓扑排序的简洁描述,将一个 有向无环图 （ DAG）中所有顶点在不违反先决条件规定的基础上排成线性序列的过程称为拓扑排序 。
示例 14 AOV-网的“死锁”现象
V2
V3
V1
V4 V5
V6
注,并非任何 AOV-网的顶点都可以排成拓扑有序序列。
若网中存在回路，则将找不到该网的拓扑有序序列 。
可以通过拓扑排序来检查 AOV-网中有无回路存在。
第七章 图第 76页任一个无回路的 AOV-网，其顶点都可以排成一个拓扑有序序列，并且其拓扑有序序列不一定是唯一的 。
对一个 AOV-网进行拓扑排序的基本步骤：
(1) 在有向图中选择一个 没有前驱的顶点 并输入之；
(2) 在图中删除该顶点和所有以它为尾的弧 ；
(3) 重复上述步骤，直至 全部顶点均已输出 或者 当前图中不存在无前驱的顶点为止 。
前者说明方案可行，而后者说明该有向图中存在回路即环。
拓扑排序的方法
V2
V3
V1
V4 V5
V6
V2
V3
V1
V4 V5
V6
第七章 图第 77页示例 15 下述有向图的一种拓扑有序序列产生过程
V1 V2
V4 V3
V6 V5
(a) AOV-网图 7.28 AOV-网及其拓扑有序序列产生的过程拓扑排序的方法
V1 V2
V4 V3
V6 V5
V1— V3— V2 — V6— V4— V5
AOV-网 存储结构的选择 可采用邻接表结构
V1 0 4 3 2 ∧
firstarc
vexdat indegree adjvex nextarc
如果在邻接表的表头结点中增加一个计数域，它记录该顶点的直接前驱结点的数目，也就是它的入度第七章 图第 78页示例 16 图 7.28(a)的有向图的邻接表
V1 V2
V4 V3
V6 V5
V1 0
V2 2 ∧
V3 1
V4 2
V5 3 ∧
V6 0
4 3 2 ∧
5 2 ∧
5 4 ∧
5 ∧
1
2
3
4
5
6
vexdat indegreefirstarcadjvexnextarc
图 7.29(a) 图 7.28(a)的有向图的邻接表顶点表 边表拓扑排序的方法第七章 图第 79页入度 indegree 域在输入时建立。每当输入一条边 <vi,vj>时
，顶点 vj的 indegree 域就增加 1。
另外，在拓扑排序过程中，当某顶点的表头结点中 indegree
域变成 0 时，需将该顶点输出，同时将该顶点的直接后继顶点的表头结点中 indegree 域减去 1。
由于入度为零的顶点在拓扑有序序列中的次序是人为地设定的
，为了方便其见，可以设置一个栈存放入度为零的顶点，每当输出便从栈中删除；反之，当出现新的入度为零的顶点则可入栈。
拓扑排序的方法第七章 图第 80页示例 13 链栈 top和 indegree 链域的变化情况模拟。 初始
V1 0
V2 2 ∧
V3 1
V4 2
V5 3 ∧
V6 0
4 3 2 ∧
5 2 ∧
5 4 ∧
5 ∧
1
2
3
4
5
6
6 1 ∧top
取走 V6 后 取走 V1 后 取走 V3 后
1 ∧top
V1 0
V2 2
V3 1
V4 1
V5 2
V6 0
2top 4 ∧
V1 0
V2 0
V3 0
V4 0
V5 1
V6 0
3top 4 ∧
V1 0
V2 1
V3 0
V4 0
V5 2
V6 0
拓扑排序的方法第七章 图第 81页示例 13 链栈 top和 indegree 链域的变化情况模拟。
初始
V1 0
V2 2 ∧
V3 1
V4 2
V5 3 ∧
V6 0
4 3 2 ∧
5 2 ∧
5 4 ∧
5 ∧
1
2
3
4
5
6
6 1 ∧top
取走 V2 后 取走 V4 后 取走 V5 后
V1 0
V2 0
V3 0
V4 0
V5 1
V6 0
top 4 ∧
取走 V3 后
2top 4 ∧
V1 0
V2 0
V3 0
V4 0
V5 1
V6 0
V1 0
V2 0
V3 0
V4 0
V5 0
V6 0
top 5 ∧ top
V6— V1— V3— V2— V4— V5
第七章 图第 82页拓扑排序算法设有向图的邻接表类型定义如下
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct VNode{
VertexType data;
int InDegree;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
第七章 图第 83页拓扑排序算法描述
Status toposort( ALGraph g )
{
FindInDegree( g ); //求各节点入度 indegree[1..vexnum]
InitStack( s );
for( i = 1; i <= g.vexnum; i++ ) //建立入度为 0的顶点的栈
if( g.vertices[i].InDegree == 0 ) Push( s,i );
count = 0;
while( !StackEmpty( s ))
{
Pop( s,i );
printf( i,g.vertices[i].data ); //输入并计数
count++;
for( p = g.vertices[i].firstarc; p; p=p->nextarc )
{ k = p->adjvex; //每个邻接点入度减 1
if( !( --g.vertices[k].InDegree )) Push( s,k );
//入度为 0，入栈
} //for
} //while
if( count < g.vexnum ) return ERROR; //有回路
return OK;
}
拓扑排序算法第七章 图第 84页关键路径术语与概念
AOE-网 若在带权有向图 G 中,顶点表示事件,有向边表示活动,权表示活动持续的时间,则称此有向图 G 为边表示活动的网（ Activity On Edge network），简称 AOE-网。
在 AOE-网中，事件与活动之间的关系：
由一个顶点发出的边所表示的所有活动，直到这个顶点所表示的事件已经发生了，才能开始。而仅当进入到这个顶点的所有边表示的活动已经完成时，该点表示的事件才能开始。
通常可用 AOE-网来研究下列问题：
1、估算工程计划的完成时间。
2、哪些活动是影响工程进度的关键表示实际工程计划的 AOE-网，应该是 无回路 的，
并且网中只有一个入度为零的顶点（ 称为源点），
也只有一个出度为零的顶点（ 称为汇点）。
第七章 图第 85页示例 19 下述 AOE-网包含 9个事件 V1,V2,···,V9，
11个活动 a1,a2,···,a11，所对应的 11个权值分别为 6,4,5,1，
1,2,9,7,4,2,4。
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
图 7.31 一个 AOE-网关键路径假定上述 AOE-网表示一个工程项目的计划。那么,事件 V1 表示整个工程开始,V9 表示整个工程结束 。事件 V5 表示活动 a4和 a5已完成，活动 a7 和 a8 可以开始。权值表示完成相应活动所需天数。
问题
(1) 完成整个工程项目至少需要多少天？
(2) 哪些活动是影响工程进度的关键？
第七章 图第 86页活动的最迟开始时间 在不推迟整个工程项目完成的 前提 下，
活动 ai 最迟必须开始进行的时间称为活动 ai 的最迟开始时间，以
l(i)表示之。
活动的时间余量 令 l(i)－ e(i) 为活动 ai 完成的时间余量。
关键活动 满足 e(i)=l(i) 的活动称为关键活动。故，关键路径上的所有活动都是关键活动。
关键路径关键路径 路径 长度最长 的路径称为关键路径（ Critical Path）。
关键路径定义了完成一个工程项目所需的最少时间,即从源点到汇点所需最长的活动持续时间之和。
活动的最早开始时间 事件 Vi 能发生的最早时间为从源点 V1 到顶点 Vi 的最长路径长，它决定了由该顶点表示的事件为尾的所有边即活动的最早开始时间。以 e(i) 表示活动 ai 的最早开始时间。
第七章 图第 87页关键路径为 V1— V2— V5— V7— V9 或者 V1— V2— V5— V8— V9
故 V9 的最早发生的时间是 18(天 )，即该工程需要 18天完成。
注,一个 AOE-网可能有多条关键路径。
示例 19 下述 AOE-网
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9图 7.31 一个 AOE-网关键路径活动 a6 的最早开始时间 e(6)=5，而最迟开始时间 l(6)=18－ 4－
4－ 2=8。
这意味着,活动 a6 推迟 3天开始或者延迟 3天完成，都不会影响整个工程项目的完成。
又,e(7)=e(8)=6+1=7,l(7)= 18－ 2－ 9=7,l(8)=18－ 4－ 7=7，即
e(7)=l(7),e(8)=l(8)。这表明,活动 a7 与 a8 的最早开始时间与最迟开始时间相同，从而 a7 与 a8 的时间余量均为 0。
第七章 图第 88页事件的最早发生时间 若活动 ai 由弧 <j,k> 表示，则从源点 V1 到顶点 Vj 的最长路径长度称为事件 Vj 的最早发生时间，
记作 ve(j)。 显然地，有 e(i) = ve(j)。
关键路径
(7-1)
事件的最迟发生时间 若活动 ai 由弧 <j,k> 表示，则称事件 Vj 最迟必须发生的时间为事件 Vj 的最迟发生时间，记作 vl(j)。
假定活动 ai 的持续时间记为 dut(<j,k>)，则有
l(i)=vl(k)－ dut(<j,k>).
综上所述,若设活动 ai 由弧 <j,k> 表示，其持续时间为
dut(<j,k>)，则有
e(i)=ve(j)
l(i)=vl(k)－ dut(<j,k>)
VkVj aidut(<j,k>)
第七章 图第 89页求事件 /活动的最早发生 /开始时间和最迟发生 /开始时间由 (7-1)，有
e(i)=ve(j)
l(i)=vl(k)－ dut(<j,k>)
其中假定活动 ai 由弧 <j,k> 表示，其持续时间为 dut(<j,k>)。
(7-1)
(1) 求 ve( j)
为求 ve(j)，从源点 V1开始，自左至右对每个事件向前计算，直至计算到汇点 Vn 为止。对于事件 Vj，仅当其所有前趋事件 Vi 均已发生且所有由边 <Vi,Vj> 表示的活动均已完成时才有可能发生。因此，有
ve(1)=0
ve(j)=Max{ve(i)+dut(<i,j>)}
i <i,j>∈ T,2≤j≤n
其中 T 是所有以 Vj 为头的弧的集合。
(7-2)
今欲推出求 事件的最早发生时间 ve 和最迟发生时间 vl 的计算公式求 ve(j) 和 vl(j) 需分向前阶段和后阶段递推地进行计算第七章 图第 90页
V1
V2a1
V3
V5
ve(1)=0,
a2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
示例 20 对于如图 AOE-网，
求各个事件的 ve。
关键路径上述计算顺序是按顶点的某一拓扑有序序列的次序进行的。
ve(2)=ve(1)＋ dut(<1,2>)＝ 0＋ 6=6,
ve(3)=ve(1)＋ dut(<1,3>)＝ 0＋ 4=4,
ve(4)=ve(1)＋ dut(<1,4>)＝ 0＋ 5=5,
ve(5)=Max{ve(2)＋ dut(<2,5>),ve(3)＋ dut(<3,5>)}=Max{6＋ 1,4＋ 1}=7,
5
ve(6)=ve(4)＋ dut(<4,6>)＝ 5＋ 2=7,
ve(7)=ve(5)＋ dut(<5,7>)＝ 7＋ 9=16,
ve(8)=Max{ve(5)＋ dut(<5,8>),ve(6)＋ dut(<6,8>)}=Max{7＋ 7,7＋ 4}=14,
ve(9)=Max{ve(7)＋ dut(<7,9>),ve(8)＋ dut(<8,9>)}
=Max{16＋ 2,14＋ 4}=18,
第七章 图第 91页
(2) 求 vl(j)
为求 vl(j)，从汇点 Vn开始，从右到左逐个事件 逆推 计算，
直到计算到源点 V1 时为止。为了尽量缩短工程的工期，通常把汇点事件 Vn 的最早发生时间（即工程的最早完工时间）作为 Vn
的最迟生时间。
不难推断,事件 Vj 的最迟发生时间 vl(j) 是其所有后继事件 Vk 的最迟发生时间 vl(k)与活动 <vj,vk> 的持续时间之差中的最小者，
则有
vl(n)=ve(n)
ve(j)=Min{vl(k)－ dut(<j,k>)}
k <j,k>∈ S,1≤j≤n－ 1
其中 S 是所有以 Vj 为尾的弧的集合。
(7-3)
关键路径第七章 图第 92页
vl(9)=ve(9)＝ 18,
vl(8)=vl(9)－ dut(<8,9>)＝ 18－ 4=14,
vl(7)=vl(9)－ dut(<7,9>)＝ 18－ 2=16,
vl(6)=vl(8)－ dut(<6,8>)＝ 14－ 4=10,
vl(5)=Min{vl(8)－ dut(<5,8>),vl(7)－ dut(<5,7>)}
=Min{14－ 7,16－ 9}=7,
vl(4)=vl(6)－ dut(<4,6>)＝ 10－ 2=8,
vl(3)=vl(5)－ dut(<3,5>)＝ 7－ 1=6,
vl(2)=vl(5)－ dut(<2,5>)＝ 7－ 1=6,
vl(1)=Min{vl(4)－ dut(<1,4>),vl(3)－ dut(<1,3>)
vl(2)－ dut(<1,2>}=Min{8－ 5,6－ 4,6－ 6} =0.
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
示例 21 对于如图 AOE-网，
求各个事件的 vl。
关键路径上述计算顺序是按顶点的某一拓扑有序序列的 逆序 进行的。
第七章 图第 93页示例 22 利用公式 (7-2),(7-3)以及 (7-1)可相继求得诸事件的最早、最迟开始时间，从而找出该 AOE— 网的诸关键活动并确定关键路径。对于示例 1中的 AOE— 网，可列表示如下事件 V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9
ve 0 6 4 5 7 7 16 14 18
vl 0 6 6 8 7 10 16 14 18
活动 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l - e 0 2 3 0 2 3 0 0 3 0 0
由此可得所给 AOE— 网的关键路径如下图所示（红色与兰色）
V1
V2
V5
V7
V9
V8
a1 a4
a8 a11
a10a7
2
4
9
7
16
关键路径第七章 图第 94页分析：
(1) 并非加快任何一个关键活动都可以缩短整个工程的工期，只有加快包括在 所有关键路径上 的关键活动才能达到此目的。 例如，若将 a11由 4天改为
3天，并不能使整个工期由 18天变为 17天，但若使 a1由 6天改为
4天，则整个工期可缩短至 16天；
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
关键路径
(2) 关键路径是要以变化的，提高某些关键活动的速度，有可能使原先的非关键路径变为新的关键路径，因而关键活动的速度提高是有限度的。
比如，若将 a1由 6天改成 4天，则 a2和 a5成为关键路径。如果再减 …
第七章 图第 95页上述两个计算 ve(j)和 vl(j)的递推公式必须分别在拓扑有序和逆拓扑有序的前提下进行，
即：
ve(j)必须在 Vj的所有前驱的最早发生时间求得之后才能确定，
vl(j)则必须在 Vj有所有后继的最迟发生时间求得之后才能确定。
因此，可以在拓扑排序的基础上计算 ve(j)和 vl(j)。
求关键路径的算法第七章 图第 96页求关键路径的算法求关键路径的算法思想如下：
(1) 输入 e 条弧 <j,k>，建立 AOE— 网的存储结构 — 邻接表
（这里，求关键路径与拓扑排序有紧密关系）；
(2) 从源点 V1出发，令 ve[1]=0，按拓扑有序求其余各顶点的最早发生时间 ve[j](2≤j≤n)。若网中不存在环（即回路），
则继续执行 (3)；
(3) 从汇点 Vn出发，令 vl[n]=ve[n]，按逆拓扑有序求其余各顶点的最迟发生时间 vl[j](1≤j ≤n-1)；
(4) 根据各顶点的 ve和 vl值及公式 (7-1)，
求每条弧 s的 e(s)和 l(s)。若 e(s)=l(s)，则为关键活动。
第七章 图第 97页算法说明
(1) 求 ve[k]
计算各顶点的 ve值是在拓扑排序的过程中进行的，故需对原拓扑排序算法作如下修改
a.在拓扑排序之前设初值，即令 ve[i]=0(1 ≤i ≤n);
b.在算法 中增加一个计算 Vj直接后继 Vk的最早发生时间
ve[k]的操作
if( ve[j] + dut(<j,k>) > ve[k] )
ve[k] = ve[j] + dut(<j,k>);
求关键路径的算法
(2) 求 vl[k]
为能按逆 拓 扑有序序列的顺序计算各顶点的 vl值，需记下在拓扑排序过程中求得的拓扑有序序列。故需在算法中增设一个栈以记录拓扑有序序列 ;
第七章 图第 98页修正的拓扑排序算法描述
Status toposort( ALGraph g,Stack &T )
{
FindInDegree( g,indegree ); //求各节点入度 indegree[1..vexnum]
InitStack( T ); InitStack( s ); count = 0;
ve[1..g.vexnum-1] = 0;
for( i = 1; i <= g.vexnum; i++ ) //建立入度为 0的顶点的栈
if( !indegree[i] ) Push( s,i );
count = 0;
while( !StackEmpty( s ))
{
Pop( s,j ); Push( T,j ); count++;
for( p = g.vertices[i].firstarc; p; p=p->nextarc )
{ k = p->adjvex; //每个邻接点入度减 1
if( !( --indegree[k])) Push( s,k ); //入度为 0，入栈
if( ve[j] + *(p->info) > ve[k] )
ve[k] = ve[j] + *(p->info);
} //for
} //while
if( count < g.vexnum ) return ERROR; //有回路
return OK;
} //算法 7.13
第七章 图第 99页求关键路径算法描述
Status critical_path( ALGraph G )
{ //G为有向图 输出该有向图中各项关键活动
if( !TopoSort( G,T )) return ERROR;
j = T.Top(); vl[1..G.vexnum] = ve[j]; //初始化
while( !StackEmpty( T )){ //按逆拓扑序求各顶点 vl
for( Pop(T,j),p=G.vertices[j].firstarc; p; p=p->next )
{ k = p->adjvex; dut = *(p->info);
if( vl[k] – dut < vl[j] ) vl[j] = vl[k] – dut;
}
for( j = 1; j < G.vexnum; j++ ) //求 ee,el和关键活动
for( p = G.vertices[j]; p; p->nextarc )
{ k = p->adjvex; dut=*(p->info);
ee = ve[j]; el = vl[k] – dut;
tag = ( ee == el )? ‘*’,‘’;
printf( j,k,dut,ee,el,tag ); //输出
}
}
求关键路径的算法算法分析：这两种算法的时间复杂度均为 O(n+e)；计算弧的活动最早开始时间 ee和最迟开始时间 el的时间复杂度为 O(e)；总的求关键路径的时间复杂度为 O(n+e)。
第七章 图第 100页示例 23 给定如下之 AOE— 网
V1
V2
V4
V5
V6
a1 a3
a7
a7
1
2
23
V3
2a2 a64
a5
3
a4
3 a
8
图 7.32 AOE— 网求关键路径的算法
1、若弧按逆时针方向编号，求依算法 7.13的拓扑排序序列，及各事件的最早发生时间；
2、根据逆拓扑排序序列，求各事件的最迟发生时间；
3、指出网中的所有关键路径。
解,1、拓扑排序序列，及各事件的最早发生时间；
V1 0,3,2,0,0,0 top1 V3V2
V2 0,3,2,5,6,0 top1 V5 V3
V5 0,3,2,5,6,7 top1 V3
第七章 图第 101页
V1
V2
V4
V5
V6
a1 a3
a7
a7
1
2
23
V3
2a2 a64
a5
3
a4
3 a
8
图 7.32 AOE— 网
V5 0,3,2,5,6,7 top1 V3
V3 0,3,2,6,6,7 top1 V4
V4 0,3,2,6,6,8 top1 V6
V6 0,3,2,6,6,8 top1
求关键路径的算法
V1 V2 V5 V3 V4 V6
第七章 图第 102页
V1
V2
V4
V5
V6
a1 a3
a7
a7
1
2
23
V3
2a2 a64
a5
3
a4
3 a
8
图 7.32 AOE— 网
ve,0,3,2,6,6,8
求关键路径的算法
V1 V2 V5 V3 V4 V6
2、根据逆拓扑排序序列，求各事件的最迟发生时间；
V6
8
V4
6
V3
2
V5
7
V2
4
V1
0
vl,0,4,2,6,7,8
3,根据公式 (7-1)求 ee,el
由 ee=el求关键活动。
V1,V3,V4,V6
第七章 图第 103页问题的提出交通网络中常常提出这样的问题：两地之间是否有路相连？在有多条通路的情况下，哪一条路最短？
从城 A到城 B若无直达车，则亦需选择一条途中中转次数最少的路线。
交通网络可用带权图表示，其中权值或表示城镇间的距离，
或是交通费用，或是所需时间、速度等等。
讨论带权有向图，并称路径上的第一个顶点为 源点 (Source),
最后一个顶点为 终点 (Destination)。
两种常见的最短路径问题
1,单源点的最短路径问题
2,所有顶点对之间的最短路径问题。
这里路径长度的度量是路径上边的权值之和。
最 短 路 径第七章 图第 104页单源点的最短路径问题问题：对于给定的带权有向图（有向网） D=（ V,E）和源点 v，
求从 v到 D中其余各顶点的最短路径。
示例 24 有如下之有向网 D1，其中边上各数值是边的权值，则可列表给出人始点 V0到各顶点之间的最短路径
V5
V4
V3V2
V1
V0
5
100 60
20
50
10
30
10
始点 终点 最短路径 路径长度
V0 V1 无
V2 (V0,V2) 10
V3 (V0,V4,V3) 50
V4 (V0,V4) 30
V5 (V0,V4,V3,V5) 60
第七章 图第 105页按路径长度 递增的次序 产生最短路径的 Dijkstra算法有向图 D1的按路径长度递增的次序排列的一张最短路径表
V5
V4
V3V2
V1
V0
5
始点 终点 最短路径 路径长度
V0 V1 无
V2 (V0,V2) 10
V4 (V0,V4) 30
V3 (V0,V4,V3) 50
V5 (V0,V4,V3,V5) 60
10
30
50
60
100 60
30
2010
50
10
第七章 图第 106页集合 S,表示已求得最短路径的终点的集合。 S的初态为 S=? 。
集合 V-S,尚未确定最短路径的顶点集合。
辅助向量 dist：其分量 D[i]表示当前所找到的从始点 v到终点 Vi的最短路径的长度。 dist[i]的初态为
arcs(v,vi)，若 <v,vi>∈ E
D[i] =
+∞,否则从始点 v出发的长度最短的一条 最短 路径：
D[j]=Min{D[i]| vi ∈ V}
此路径为 v到 vj。可把顶点 Vj加入到 S中。
下一条长度 次短 的最短路径：设终点是 Vk，则此路径或者是 v-vk，
或者 v-vj-vk。将 vk亦加入到 S中。
一般情况下，有,下一条最短路径（设其终点为 x）或者是 v-x
，或者是中间只经过 S中的顶点而最后到达顶点 x的路径 。
按路径长度 递增的次序 产生最短路径的 Dijkstra算法第七章 图第 107页
Dijkstra 算法思想
(1) 邻接矩阵 arcs来表示带权有向图，若 <vi,vj>不存在，则置
arcs[i,j] 为 ∞。 S为已找到从 v出发的最短路径的终点的集合，它的 初始状态为空集 。 D[i]的初态为
arcs(v,vi)，若 <v,vi>∈ E
D[i]=
+∞,否则
(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] k? V-S
则修改 dist[k]为 D[k] = D[j]+arcs[j][k]
(4) 重复操作 (2),(3)共 n-1次。由此求得从 v到图上其余各顶点的最短路径是依路径长度递增的序列。
按路径长度 递增的次序 产生最短路径的 Dijkstra算法第七章 图第 108页示例 25 有向网 D1及其带权邻接矩阵为有向图 D1
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
按 Dijkstra算法，可列表表示从源点 V0到其余各顶点的最短路径，以及运算过程中
arcs向量的变化：
终点 从 v 0 到各终点的 d i s t 值和最短路径
V 1 ∞ ∞ ∞ ∞ ∞无
V 2
10
V 0 - V 2
V 3 ∞
6 0
V 0 - V 2 - V 3
5 0
V 0 - V 4 - V 3
V 4
30
V 0 - V 4
30
V 0 - V 4
V 5
10 0
V 0 - V 5
10 0
V 0 - V 5
9 0
V 0 - V 4 - V 5
6 0
V 0 - V 4 - V 3 - V 5
V j V 2 V 4 V 3 V 5
V5
V4
V3V2
V1
V0
5
100 60
20
50
10
30
10
第七章 图第 109页
void shortpath_DIJ( Mgraph G,int v0,ShortPathTable &D)
{
for( v = 1; v <= G.vexnum; v++ )
{ final[v] = false; D[v] = G.arcs[v0][v];
}；
D[v0] = 0; final[v0] = true;
for( i = 2; i <= G.vexnum; i++ )
{ min = ∞ ;
for( w = 1; w < G.vexnum; w++ )
if( !final[w] ) //w在 V-S中
if( D[w] < min ) { v = w; min = D[w] }
final[v] = true;
for( w = 1; w < G.vexnum; w++ )
if( !final[w] && ( min + G.arcs[v][w] < D[w] ))
D[w] = min + G.arcs[v][w];
}
} //shortpath_DIJ 算法分析：时间复杂度 O(n2)
第七章 图第 110页问题：对于给定的有向图 G=(V,E)，要对 G中任意一对顶点有序对 v,w(v≠w)，找出 v到 w的最短路径。
方法一 依次把有向图 G的每个顶点作为源点，重复执行 Dijkstra算法 n次，即可求得每一对顶点之间的最短路径。其时间复杂度是 O(n3)。
方法二 采用一种更为直接的方式，计算每一对顶点之间最短路径，即由 Floyd提出的一种算法，其时间复杂度虽仍是 O(n3)，但形式上却较为简单。
Floyd算法中仍采用带权邻接矩阵以表示一个有向网。
每一对顶点之间的最短路径第七章 图第 111页分析：如何求 Vi到 Vj的最短路径？
对于 1≤i,j≤n,若 Vi到 Vj 有弧，则 Vi到 Vj 存在一条长度为
cost[i,j]的路径，但它不一定是最短路径，因为可能存在一条从 Vi
到 Vj但包含其它顶点为中间点的路径。应该依次考虑 Vi到 Vj 能否有以顶点 1,2,…,n 为中间点的更短路径 。
(1) 首先考虑从 Vi到 Vj 是否有以顶点 V1为中间点的路径，即
Vi— V1— Vj若有，则取 Vi— Vj与 Vi— V1— Vj中路径长度较短者，作为从 Vi到 Vj的中间顶点的 序号不大于 1的最短路径；
每一对顶点之间的最短路径必须先求出所有顶点对 (Vi,Vj)的中间顶点的 序号不大于 1的最短路径，才能进行 (2)。
(2) 其次考虑从 Vi到 Vj 是否有包含顶点 V2为中间点的路径，即
Vi-… -V2-…V j,如果 Vi-… -V2和 V2-… -Vj分别是当前找到的中间顶点的序号不大于 1的最短路径，那么 Vi-… -V2-…V j.就有可能是从 Vi到
Vj的中间顶点的序号不大于 2的最短路径。将它与已经得到的从 Vi
到 Vj的中间顶点序号不大于 1的最短路径相比较,从中选出中间顶点的序号不大于 2的最短路径；
第七章 图第 112页
(3) 依次类推。一般地，若 Vi-… -Vk 和 Vk -…V j.分别是 从 Vi到 Vk
和从 Vk到 Vj的中间顶点的序号不大于 k-1的最短路径,则将 Vi-… -Vk-
…V j和已得到的从 Vi到 Vj且中间顶点序号不大于 k-1的最短路程相比较，取其短,则是从 Vi到 Vj且中间顶点序号不大于 k的最短路程 ；
每一对顶点之间的最短路径
(4) 经过 n次比较后，最后求得的必是从 Vi到 Vj的最短路径；
实现上述算法的关键,要保留每一步求得的、所有顶点对之间的当前最短路径长度。为此，定义一个 n阶方阵序列 A(0),A(1)，
···,A(n),其中
A(0)[i,j]=cost[i.j]
A(k)[i,j] = Min{A(k-1)[i,j],A(k-1)[i,k]+A(k-1)[k,j]},1≤k≤n
这里,A(k)[i,j]表示从 Vi到 Vj的中间顶点的序号不大于 k的最短路径长度。故 Floyd算法的基本思想是：从 A(0)开始，递推地生成矩阵序列 A(1),A(2),··,A(n)。
第七章 图第 113页
Floyd 算法描述
void shortpath_FLOYD( Mgraph G,PathMatrix P[],
DistanceMatrix &D )
{//最短路径 P，带权长度为 D。如果 P[v][w][u]=true则 v,w是最短路径顶点
for( v =1; v <= G.vexnum; v++ )
for( w = 1; w <= G.vexnum; w++ ){
D[v][w] = G.arcs[v][w];
for( u = 1; u <= G.vexnum; u++ ) P[v][w][u] = false;
if( D[v][w] < ∞ )
{ P[v][w][v] = ture; P[v][w][w] = true; }
};
for( u = 1; u <= G.vexnum; u++ )
for( v = 1; v <= G.vexnum; v++ )
for( w = 1; w <= G.vexnum; w++ )
if( D[v][u]+ D[u][w] < D[v][w] )
{ D[v][w] = D[v][u] + D[u][w];
for( i = 0; i <= G.vexnum; i++ )
P[v][w][i] = P[v][u][i] || P[u][w][i];
};
} //shortpath_FLOYD
第七章 图第 114页示例 26 设带权有向图 D2及对应的邻接矩阵如下所示
1 2
3
6
4
b
2
11
a
3
c(a) (b)
0 4 11
6 0 2
3 ∞ 0
当 i=j时 D[i,j]=0，即对角线上元素为零
A
(0 )
A
( 1 )
A
(2 )
A
(3 )
A
1 2 3 1 2 3 1 2 3 1 2 3
1 0 4 11 0 4 11 0 4 6 0 4 6
2 6 0 2 6 0 2 6 0 2 5 0 2
3 3 0 3 7 0 3 7 0 3 7 0
P A T H
( 0 )
P A T H
( 1 )
P A T H
( 2 )
P A T H
( 3 )P A T H
1 2 3 1 2 3 1 2 3 1 2 3
1 AB AC AB AC AB A B C AB A B C
2 BA BC BA BC BA BC BCA BC
3 CA CA C A B CA C A B CA C A B
图 7.39图 7.38中有向图的各对顶点间的最短路径及其路径长度第七章 图第 115页示例 27 对下述有向图
100
60
10
30
1050
20
V1
V5
V4V3
V2
可写出 A(0),A(1)，
A(2),···,A(5)诸递推矩阵的内容
A(1) =A(0)
0 10 ∞ 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0
A(0)=
A(5) =A(4)
A(2)=
0 10 60 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0
A(4)=
0 10 50 30 60
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0
0 10 60 30 70
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0
A(3)=
第七章 图第 116页第七章 图 小结内容提要
● 图的定义和术语
● 图的存储结构 —— 数组表示法（邻接矩阵）、邻接表
、十字链表、邻接多重表
● 图的遍历 —— 深度优先搜索、广度优先搜索
● 构造连通图的最小生成树的 Prim 算法的
Kruskal 算法
● AOV-网及拓扑排序
● AOE-网及关键路径
● 有向网的最短路径问题
● 两类求最短路径的算法 —— Dijkstra 算法和
Floyd 算法第七章 图第 117页第七章 图 小结学习要点
● 熟悉图的有关术语和概念
● 熟悉图的各种存储结构，并能根据问题的要求选择合适的存储结构
● 掌握遍历图的两种算法
● 掌握求最小生成树、拓扑排序、关键路径以及最短路径的各种算法
● 了解图的基本应用
第七章 图
(重点 )
第七章 图第 2页主要内容
图的概念
图的存储结构数组表示法 —— 邻接矩阵邻接表表示法十字链表表示法邻接多重表表示法
图的遍历深度优先搜索广度优先搜索第七章 图第 3页主要内容
图的连通性问题无向图的连通分量和生成树构造最小生成树的 Prim算法构造最小生成树的 Kruskal算法
有向无环图
拓扑排序
关健路径
最短路径第七章 图第 4页第七章 图
内容和要求图及其有关的基本概念、图的存储结构及其图的遍历，
最短路径、拓扑排序的关健路径，动态存储管理。要求获得有关图结构及其应用方面的初步知识和经验。理解图及其有关的基本概念，图的存储方法，熟悉遍历图的深度优先（
DFS）和广度优先（ BFS）的搜索算法，了解最短路径、拓扑排序、关健路径的方法及算法的基本思想。
重点图的三种常用的存储表示,DFS法和 BFS法。难点是图的邻接多重存储表示,DFS法和 BFS法，最短路径。
第七章 图第 5页什么是图图形结构是一种较 线性表结构 和 树形结构 更为复杂的 非线性数据结构 。 在人工智能、工程、数学、物理、
化学、计算机科学等学科领域中，图形结构均有着广泛的应用。
线性表结构,数据元素即结点之间仅有线性关系。
树形结构,数据元素之间具有明显的层次关系。每层中的结点可允许有若干个孩子结点，但 仅 允许有一个双亲结点（前趋）。
图形结构,数据元素之间的关系是 任意的,图中任意两个结点之间都可能相关。
事实上，树形结构是图形结构的一种特殊情况。
图的概念第七章 图第 6页图常用来解决的几类主要问题
1,模拟计算机与通信网络的联接；
2,表示一张地图的一组坐标以及坐标之间的距离，以求得最短路径；
3,模拟交通网络的流量；
4,寻找从开始状态到目标状态的路径，如人工智能问题求解；
5,模拟计算机算法，显示程序状态的变化；
6,为复杂活动各子任务的完成寻找顺序，如大型建筑的建造；
… … … …
图的概念第七章 图第 7页定义,图是一种数据结构，它的形式化定义为
Graph=(V,R)
其中
V={x|x∈ dataobject}
R={VR}
VR={＜ x,y＞ | P(x,y)∧ (x,y ∈ V)}
可以简记为
G=（ V,E）
其中 V是顶点的有穷非空集合,E是 V中顶点的偶对（称为边）的有穷集。
通常亦可将图 G的顶点集和边集分别记作 V(G)和
E(G)。
若 E(G)为空集，则表示图 G仅有顶点而没有边。
图的定义第七章 图第 8页示例 1 有向图 G1和无向图 G2
G1
G2
图的定义
V(G1)={v1,v2,v3,v4}
E(G1)={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}
V(G2)={v1,v2,v3,v4,v5}
E(G2)={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}
V1 V2
V3 V
4
V1 V2
V4 V5
V3
第七章 图第 9页顶点,图中的数据元素。
弧,有向边，用以尖括号括起来的 有序对 <vi,vj>表示。
弧尾,有向边 <vi,vj>的始点 vi。
弧头,有向边 <vi,vj>的终点 vj。
有向图,图 G中每条边都是有向边（ 弧 ）。
无向图,图 G中每条边都是没有方向的，这些边用以
(vi,vj )形式的 无序对 表示 。
图的术语
V1 V2
V3 V
4
V1 V2
V4 V5
V3
第七章 图第 10页图的顶点数 n和边数 e的关系,对有向图,0≤e≤n(n-1)；对无向图,。
有向完全图,恰有 n(n-1)条有向边（即弧）的有向图。
无向完全图,恰有 条无向边的无向图。
稀疏图,图中边或弧的数目 e<<n2。
稠密图,图中边或弧的数目 e≈n2（准确地说，无向图的 e 接近于,有向图的 e接近于 n(n-1)。
)1(210 nne
)1(21?nn
)1(21?nn
图的术语
V1 V2
V3 V
4
V1 V2
V4 V5
V3
第七章 图第 11页子图,设有两个图 G=(V,E)和 G`=(V`,E`)，如果 V` V,E` E,
则称 G`为 G的子图 。
邻接点,若无向边 (v,v`)∈ E，则称顶点 v和 v`互为邻接点。
关联,称无向边 (v,v`)与顶点 v和 v`相关联。
顶点 V的度,与 v相关联的边的数目，记为 TD(v)。
顶点 V的入度,有向图中，以顶点 V为弧头（即终端点）的弧的数目，记为 ID(V)。
顶点 V的出度,有向图中，以顶点 V为弧尾（即初始点）的弧的数目，记为 OD(V)。
示例 2 有向图 G1,顶点数目 n=4；有向边或弧的数目 e=4； ID(V1)=1,OD(V1)=2,TD(V1)=3。
无向图 G2,顶点数目 n=5；无向边的数目 e=6； TD(V1)=2。
注,一个有 n个顶点，
e条边或弧的图，有：
).(21
1
n
i
iVTDe
图的术语
V1 V2
V3 V4
G1
V1 V2
V4 V5V3
G2
第七章 图第 12页路径,图 G中由顶点 V到 V`的路径是一个顶点序列
V=Vi0,Vi1,···,Vim=V`，其中 (Vij-1,Vij)∈ E,1≤j≤m。若图 G是个有向图
，则由顶点 V到 V`的路径亦是有向的，它由 E(G)中的有向边
<Vij-1,Vij>∈ E,1≤j≤m组成。
路径的长度,图 G中由顶点 V到 V`的路径长度是指在该路径上的边或弧的数目。
简单路径,若图 G中由顶点 V到 V`的一条路径上，除了 V和 V`
可以相同外，其余顶点均不相同，则称此路径为一条简单路径。
简单回路,起点 V和终点 V`相同的简单路径。亦称简单环。
回路或环,起点 V和终点 V`相同的路径。其余顶点允许重复出现。
示例 3 下述有向图 G3和无向图 G4
G3,顶点序列 V1,V2,V1是一个长度为 2的有向简单环； V1,V2,V3是由顶点 V1到 V3的长度为 2
的有向简单路径
G4,V1,V2,V3,V4是由 V1到 V4长度为 3简单路径
V1
V2 V3
V4
V1
V2
V3
G3 G4
第七章 图第 13页有根图,在一个有向图中，若存在一个顶点 V，从该顶点有路径可以到达图中其他所有顶点，则称此有向图为有根图，顶点 V称作该图的根。
连通,在无向图 G中，如果从顶点 V到顶点 V`有路径，则称 V和
V`是连通的。
连通图,若在无向图 G中,V(G)的任意两个不同的顶点 Vi和 Vj
都连通（即有路径），则称 G为连通图。
连通分量,无向图 G的极大连通子图称为 G的连通分量。显然
，任何连通图的连通分量只有一个，即是其自身。而非连通的无向图却有多个连通分量。
强连通图,在有向图 G中，若对于 V(G)中任意两个不同的的顶点 Vi和 Vj，都存在从 Vi到 Vj和从 Vj到 Vi的路径,则称 G是强连通图。
强连通分量,有向图 G的极大强连通子图称为 G的强连通分量
图的术语第七章 图第 14页强连通只有一个强连通分量，即是其自身。非强连通的有向图有多个强连通分量。
示例 5 设有下列图
V1
V2 V3
V4
V1
V2
V3
V1
V2 V3
V4 V6V5 V7
V1
V2 V3
V4
V5
V6 V7
V8有向图 G3 无向图 G4 无向图 G5
无向图 G6
则 G4与 G5均是连通图。
G6是非连通图，但它有两个连通分量 H1和 H2。
G3不是强连通图，因为 V3到 V2没有路径。但 G3有两个强连通分量，如下所示 V1
V2
V3
网,若将图的每条 边或弧 都赋上一个权，则将 这种带权的图称为网络，或简称网。 通常权是具有某种意义的数，比如它们可以表示两个结点之间的距离、耗费、流量等。
图的术语第七章 图第 15页示例 4 有关图的术语图解示例
0
1 3
2
4
4 1
1
2
3 7
⑴ 一个图 ⑵ 一个有向图
⑶ 一个有向标号图，且边上标有权。
简单路径：顶点 0→ 顶点 1 → 顶点 3 → 顶点 2。
非简单路径：顶点 0→ 顶点 1 → 顶点 3 → 顶点 2 → 顶点 4 → 顶点 1。
简单回路：顶点 1 → 顶点 3 → 顶点 2 → 顶点 4 → 顶点 1。
（ 1）
图的术语
（ 2） （ 3）
第七章 图第 16页示例 6 如下是一个网生成树,一个 连通图 G的子图如果是 一棵包含 G的所有顶点的极小连通子图，则该子图称为 G的生成树。 所谓极小是指边数最少。由于 n个顶点的连通图至少有 n-1条边，而所有包含 n-1边及 n个顶点的连通图都是无回路的树，所以生成树是无回路的树。若在生成树中去掉任何一条边，都会使之变为非连通图。若在生成树上任意添加一条边，就必定出现回路。
V1
V3
V2
V4
V5
11
10
3
2
8
65 4
图的术语第七章 图第 17页示例 7 设有如下无向图 G
1 2A
13
3 54
B
L M
C D E
12
6 87
F G H
9 1110
I J K
图 7.3 无向图及其连通分量则
(1) 无向图 G是一个非连通图
(2) 无向图 G有三个连通分量，分别为
A B
L M
C
F
J
D E
I K
G H
(3) 图 7.5是无向图 G中大连通分量的一棵生成树 A B
L M
C
F
J
图 7.5注,一棵有 n个顶点的生成树有且仅有 n-1条边，但是有 n-1
条边的图不一定是生成树。
图的术语第七章 图第 18页有向树,如果一个有向图恰有一个顶点的入度为 0，其余顶点的入度均为 1，则是一棵有向树。
生成森林,一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
示例 8 如下表示一个有向图及其生成森林
A
F E
B
D
C
F
A
B
E
D
C
图 7.6 一个有向图及其生成森林
图的术语第七章 图第 19页
(1) LocVertex(G,v) 顶点定位函数确定顶点 v在图 G中的位置。若图中无此顶点，则返回函数值 0。
(2) Get Vertex(G,i) 取顶点函数求图 G中第 i个顶点。若 i大于图 G中的顶点数，则返回函数值 NULL。
(3) FirstADJ(G,v) 求第一个邻接点函数求图 G中顶点 v的第 1个邻接点。若 v没有邻接点或图 G中无顶点 v,则返回函数值 0。
(4) NextADJ(G,v,w) 求下一邻接点函数已知 w为图 G中顶点 v的某个邻接点，求顶点 w的下一个邻接点。若 w是 v的最后一个邻接点，则返回函数值 0。
(5) InsVertex (G,u)插入顶点操作和图 G中增添一个顶点 u为图 G的第 n+1个顶点，其中 n为插入之前图 G中所含顶点的个数。
图的基本操作第七章 图第 20页
(6) InsARC(G,v,w) 插入弧的操作在图 G中增添一条从顶点 v到顶点 w的弧。
(7) DelVertex(G,v) 删除顶点操作在图 G中删除顶点 v以及所有与顶点 v相关联的弧。
(8) DelARC(G,v,w) 删除弧的操作在图 G中删去一条从顶点 v到顶点 w的弧。
以上有关图的若干基本操作，前四种不涉及图的修改，后四种涉及图的修改。在后面讨论图的存储结构及图的操作中，主要考虑图的前四种基本操作。
图的基本操作第七章 图第 21页图的存储表示方法方法很多。对应于不同的应用问题，
往往选用不同的图的存储结构。具体选择哪一种表示法，主要取决于具体的应用场合以及欲施加的操作。
介绍一般情况下常用的图的有关存储结构。它们是数组表示法 —— 邻接矩阵邻接表表示法 —— 图的一种链式存储结构十字链表表示法 —— 有向图的另一种链式存储结构邻接多重表表示法 —— 无向图的另一种链式存储结构
图的存储结构第七章 图第 22页数组表示法 —— 邻接矩阵邻接矩阵 （ Adjacency Matrix）是表示图中顶点之间相邻关系的矩阵。
设 G=(V,E)是具有 n个顶点的图，则 G的邻接矩阵是具有如下性质的 n阶方阵
中的边不是或若 中的边是或若 )(,),(,0 )(,),(,1,GEvjvivjvi GEvjvivjvijiA
示例 9 设有向图 G1和无向图
G2为
V1 V2
V3 V4
V1 V2
V4 V5
V3
则它们的邻接矩阵 A1和 A2分别为有向图 G1 无向图 G2
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 0 0
A1= A2=
图的存储结构 – 邻接矩阵第七章 图第 23页说明
(1) 无向图的邻接矩阵是对称的，有向图则不一定；
(2) 设图 G共有 n个顶点，则若 G是有向图，则存储空间为 n2位，
而若 G是无向图，则存储空间可为 n(n+1)/2位，即仅存储上（或下）
三角元素；
(3) 无向图顶点 Vi的度是邻接矩阵中第 i行（或第 i列）的元素之和，
即而有向图顶点 Vi的出度为邻接矩阵中第 i行元素之和，入度为第 i列元素之和，即示例 10 对于下述之无向图 G7和有向图 G8
V1 V4
V2 V3
V1 V2
V5 V4
记其相应邻接矩阵分别为 A7和 A8，则有无向图 G7 有向图 G8
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
0 1 0 0 0
1 0 0 0 1
0 1 0 1 0
1 0 0 0 0
0 0 0 1 0
A7= A8=
V3
)],[(];,[)(
11
n
j
n
ji
ijAorjiAVTD
n
j
n
j
ii ijAVIDjiAVOD
1 1
],[)(],,[)(
第七章 图第 24页
(4) 欲检测在图 G中总共有多少条边，必须按行、列逐次检测邻接矩阵的各元素，故最坏情况下需时 O(n2)。
若 G是网，则邻接矩阵可定义为
否则或或若
0
);(,),(,],[ GEVVVVwjiA jijiij
其中 wij表示边上的权值,∞表示一个计算机允许的、大于所有边上权值的数。
示例 11 下面给出一个网及其邻接矩阵
V1 V2
V5
V3 V4
3
8
6
5 4
2
11
10
∞ 3 5 8 ∞
3 ∞ 6 4 11
5 6 ∞ 2 ∞
8 4 2 ∞ 10
∞ 11 ∞ 10 ∞
A=
无向网示例 12 有向网及其邻接矩阵（图 7.9）
3
5
48
7 9
61
5
5
V4
V3
V2V1
V6
V5
∞ 5 ∞ 7 ∞ ∞
∞ ∞ 4 ∞ ∞ ∞
8 ∞ ∞ ∞ ∞ 9
∞ ∞ 5 ∞ ∞ 6
∞ ∞ ∞ 5 ∞ ∞
3 ∞ ∞ ∞ 1 ∞
A=
图 7.9
第七章 图第 25页下面给出建立无向网的存储结构即邻接矩阵的算法。
数据结构
#define MAX_VERTEX 20 //最大顶点个数
typedef enum{DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网
typedef struct ArcCell{
VRType adj; //顶点关系类型，无权图用 0,1表示相邻否，带权图为权
InfoType *info; //相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX+1][MAX_VERTEX+1];
typedef struct{
VertexType vexs[MAX_VERTEX+1]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //顶点数，弧数
GraphicKind kind; //图的类型
} Mgraph;
图的存储结构 – 邻接矩阵数组表示法 —— 邻接矩阵第七章 图第 26页算法描述
Status CreateGraph( Mgraph &G )
{ //建立无向网的数组型存储结构
for( i=1; i <= G.vexnum; i++ )
scanf( &G.vexs[i] ); //输入 n个顶点的信息
for( i=1; i <= G.vexnum; i++ )
for( j=1; j <= G.vexnum; j++ )
G.arcs[i][j] = ( ∞,NULL ); //初始化
for( k=1; k < G.arcnum; k++ )
{ scanf( &v1,&v2,&w); //输入一条边的信息,w为与边相关的权
i = LocVertex( G,v1 );
j = LocVertex( G,v2 ); //确定 v1,v2在 G中的位置
G.arcs[i][j].adj = w;
G.arcs[j][i].adj = w //假设无其它和边相关的信息
}
} //CreateGraph 算 法 7.1
注,时间复杂度为 O(n2+e·n).
图的存储结构 – 邻接矩阵第七章 图第 27页说明可在前述数组型存储结构下实现诸如 FirstADJ
(G,v)的基本操作。
先由 LocVertex(G,v)找到顶点 v在 G中的位置，即 v
在一维数组 vexs中的序号 i，则二维数组 Arcs中第 i行上第一个 adj域的值为 1的分量所在列号 j，便为所求顶点 v
的第一个邻接点在图 G中的位置。
同理，求 NextADJ(G,v)便为 j列之后第一个 adj域的值为 1的分量所在列号。
图的存储结构 – 邻接矩阵第七章 图第 28页邻接表 (Adjacency List)表示法类似于树的孩子链表表示法。它是图的一种链式存储结构。
对于图 G中的每个顶点 Vi，该方法把所有邻接于 Vi的顶点链成一个单链表，这个单链表就称为该顶点 Vi的邻接表。
结点形式
(1) 边或弧的结点
adjvex：邻接域，指示与顶点 Vi邻接的点在图中的位置
nextarc：链域，指示下一条边或弧的结点
info：数据域，存储和边或弧相关的信息
(2) 顶点结点
vexdata：数据域，存储顶点 Vi的名或其他有关信息
firstarc：链域，指向链表中第一个结点，这些顶点结点通 常以顺序结构（向量）的形式存储，以便随机地访问任一顶点的链表。
adjvex nextarc info
vexdata firstarc
邻接表表示法第七章 图第 29页
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
邻接表表示法
V1 V2
V4 V5
V3
无向图 G2
对无向图 G2,若输入序对分别为 1,2; 1,4; 2,3; 2,5;3,4; 3,5；可得示例：
第七章 图第 30页下面给出建立无向图的邻接表表示存储结构的算法。
数据结构
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex; //顶点的位置
struct ArcNode *nextarc; //下一个顶点的指针
InfoType *info; //其它信息
}ArcNode;
typedef struct VNode{
VertexType data; //数据
ArcNode *firstarc; //指向相邻顶点的链表
}VNode,AdjList[MAX_VERTEX_NUM+1];
typedef struct{
AdjList vertices; //顶点向量
int vexnum,arcnum;
int kind;
}ALGraph;
邻接表表示法第七章 图第 31页算法描述
Create_adjlist( ALGraph &ga,int n,int e )
//建立无向图的邻接表
{ for( i=1; i<=n; i++ )
{ scanf(ga.vertices[i].data);
ga.vertices[i].firstarc = NULL; ga.vexnum = n }
for( k=1; k <= e; k++ )
{ scanf(i,j); //读入边 (vi,vj)的顶点对序号
s = new(ArcNode); //生成邻接点序号为 j的边表结点 s
s->adjvex = j; s->nextarc=ga.vertices[i].firstarc;
ga.vertices[i].firstedge = s; //插表头
s = new(ArcNode); //生成邻接点序号为 i的边表结点 s
s->adjvex = i;
s->nextarc=ga.vertices[j].firstarc;
ga.vertices[j].firstarc = s; //插表头
}
ga.arcnum = e;
} //Create_adjlist
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
邻接表表示法
V1 V2
V4 V5
V3
无向图 G2对无向图 G2,若输入序对分别为 1,2; 1,4; 2,3; 2,5;3,4; 3,5；可得第七章 图第 32页说明
(1) 邻接表中顶点结点是有序的,以向量存储 ；
(2) 无向图 的邻接表，第 i个结点的度为第 i个链表的结点数；而在有向图中，第 i个链表的结点数仅是顶点 Vi的出度。为求入度，必须遍历整个表。在所有链表中其邻接点域的值为 i的结点的个数是顶点 Vi的入度；
(3) 如需确定顶点的入度，可建立一个有向图的逆邻接表
，即对每个顶点 Vi建立一个邻接以 Vi为头的弧的表；
(4) 称无向图的邻接表为 边表 ；称有向图的邻接表为 出边表 ；称有向图的逆邻接表为 入边表 ；
邻接表表示法
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
第七章 图第 33页说明邻接表表示法
(5) 对于一个具有 n个顶点 e条边的图 G，若 G是无向图，则它的邻接表表示中有 n个顶点表结点和 2e个边表结点；若 G是有向图，则它的邻接表表示或逆邻 接表表示中均有 n个顶点表结点和 e个边表结点；
(6) 邻接矩阵与顶点数 n有关，故在边数很多即
e<<n2时，宜采用邻接表表示法。
V1 4 2 ∧
V2 5 3
V3 5 4
V4 3 1 ∧
V5 3 2 ∧
1 ∧
2 ∧
1
2
3
4
5
第七章 图第 34页十字链表 (Orthogonal List) 是有向图的另一种链式存储结构。
用十字链表存储 有向图,实际上就是将有向图的邻接表和逆邻接表结合起来得到的一种链表。
十字链表中的结点形式
(1) 弧结点 <Vi,Vj>
tailvex：尾域，指示弧尾顶点 Vi在图中的位置
headvex：头域，指示弧头顶点 Vj在图中的位置
hlink：链域，指向以 Vj为弧头的下一条弧
tlink：链域，指向以 Vi为弧尾的下一条弧弧头相同的弧在同一链表上，弧尾相同的弧也在同一链表上。
(2) 顶点结点 Vi
data：数据域，存储和顶点相 关的信息
firstin：链域，指向以 Vi为弧头的第一个弧结点
firstout：链域，指向以 Vi为弧尾的第一个弧结点
tailvex headvex hlink tlink
data firstin firstout
十字链表表示法第七章 图第 35页
#define MAX_VERTEX_NUM 20
typedef struct ArBox{
int tailvex,headvex;
struct ArBox *hlink,*tlink;
}ArcBox;
typedef struct VexNode{
VertexType data;
ArcBox *firstin,*firstout;
}VexNode;
typedef struct{
VexNode xList[MAX_VERTEX_NUM];
int vernum,arcnum;
}OLGraph;
十字链表表示法
V1 V2
V3 V4
V1 1 2 1 3 ∧
V2 ∧
V3 3 1 3 4 ∧
V4 4 1 4 2 4 3 ∧∧∧
∧
∧
1
2
3
4
图 7.11 有向图的十字链表示例 13,一有向图及其对应的十字链表第七章 图第 36页算法描述
Status Create_ortho( OLGraph &G)
{ //建立有向图的十字链表存储结构
scanf( &G.vexnum,&G.arcnum ); //输入顶点和弧的数目
for( i = 1; i <= G.vexnum; i++ )
{ scanf(G.xlist[i].data); //输入顶点信息
G.xlist[i].firstin=NULL;
G.xlist[i].firstout=NULL //指针初始化
};
for( k = 1; k <= G.arcnum; k++ )
{ scanf( &vt,&vh ); //输入弧的信息
i=LocVertex(G,vt); j=LocVertex(G,vh);
//确定弧尾和弧头在图中的位置
p = new(ArcBox); p->tailvex = i; p->headvex = j;
p->hlink = G.xlist[j].firstin;
G.xlist[j].firstin = p;
p->tlink = G.xlist[i].firstout;
G.xlist[i].firstout = p;
//将弧结点分别插入在两个链表中
}
} //Create_ortho 算 法 7.2
十字链表表示法第七章 图第 37页邻接多重表（ Adjacency Multilist）是 无向图 的另一种 链 式存储结构。
在无向图的邻接表表示法中，每条边 (Vi,Vj)是用两个结点表示的，分别在第 i个和第 j个链表中。这给图的某些操作（如检测某条边是否被访问即搜索过、删去一条边等）带来不便。
此时，若采用 邻接多重表表示法 则更为方面适宜。
邻接多重表的结点形式
(1) 边结点
mark：标志域，用以标记该条边是否被搜索过
ivex,jvex：该边依附的两个顶点在图中的位置
ilink,jlink：链域，分别指向下一条依附于顶点 ivex,jvex的边
(2) 顶点结点
data：数据域，存储和该顶点相关的信息
firstedge：链域，指示第一条依附于该顶点 Vi的边
mark ivex ilink jvex jlink
data firstedge
邻接多重表表示法第七章 图第 38页
#define MAX_VERTEX_NUM 20
typedef enum{unvisited,visited} VisitIF;
typedef struct Ebox{
VisitIF mark;
int ivex,jvex;
struct Ebox *ilink,*jlink;
InfoType *info;
}Ebox;
typedef struct VexBox{
VertexType data;
Ebox *firstedge;
}VexBox;
typedef struct{
VexBox adjmulist[MAX_VEXTEX_NUM];
int vexnum,edgenum;
}AMLGraph;
V1 V2
V4 V5
V3
无向图 G2
注,表示法不唯一邻接多重表表示法
V1
V2
V3
V4
V5
1 2 1 ∧ 4
3 2 3 4
5 2 3 5
∧
∧ ∧∧
1
2
3
4
5
图 7.12 无向图 G2
的邻接多重表第七章 图第 39页图的遍历（ graph traversal）,从图的某一顶点出发，沿着某条搜索路径，对图中所有顶点各作一次访问。
连接图的遍历,从图中任一顶点出发，顺着边可访问到该图中所有的顶点。
非连通图的遍历,需多次调用搜索过程。
遍历图较遍历树的复杂性,为了避免重复访问同一顶点，
必须记住每个顶点是否曾被访问过。
两种常用的遍历图的方法,深度优先 搜索遍历和 广度优先搜索遍历。它们对无向图和有向图均适用。
图的遍历算法,它是求解图的连通性问题、拓扑排序和求关健路径等算法的基础。
图的遍历第七章 图第 40页图的深度优先搜索 （ Depth-first search，简记为 DFS）遍历是 树的先根遍历的推广 。
算法思想,设给定图 G的初始状态是所有顶点均未曾被访问。
(1)以图 G中某一顶点 V0为初始出发点，首先访问该出发点 V0，
并将其标记为已访问的,(2)选取与 V0邻接的未被访问的任一顶点 W
访问之并作标记,(3)再选取与 W邻接的未被访问的任一顶点访问之并作标记，依次类推，重复上述访问。
当即达到一个顶点时，则又从最后被访问的且尚有邻接顶点未被访问过的顶点，重复上述搜索过程，直到所有的被访问顶点的邻接顶点都被访问过为止。
显然，上述搜索过程是 递归定义 的，其搜索次序体现了优先向纵深发展 的趋势，故此搜索法被称之为 浓度优先搜索法 。
深度优先搜索（ DFS）遍历第七章 图第 41页示例 1 无向图 G4及其浓度优先搜索的过程
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
1 5 1
7V6
V7
3
V4
2 V
8
4 V
5
2 8
(a) 无向图 G4
图 7.3 遍历图的过程
(b) 深度优先搜索的过程所得的顶点访问序列为
V1→ V 2→ V 4→ V 8→ V 5→ V 3→ V 6→V 7
深度优先搜索（ DFS）遍历第七章 图第 42页图的深度优先搜索遍历算法
void DFSTraver( Graph g )
{ //对图 g按深度优先进行遍历
for( vi=1; vi <= vexnum; vi++ )
visited[vi]=false; //标志数组初始化
for( vi=1; vi <= vexnum; vi++ )
if(!visited[vi]) dfs(g,vi) //调用从 vi出发遍历的递归过程
} //DFSTraver 算法 7.3
void dfs( Graph g,int v )
{ //从 vo出发深度优先遍历图 g
visite(v); //printf(v)
visited[v]=true;
for( w=FirstAdj(g,v); w; w=NextAdj(g,v)) //w为 vo的邻接点
if( !visited[w]) dfs(g,w);
} //dfs 算法 7.4
第七章 图第 43页算法分析
(1) 为了在遍历过程中便于区分顶点是否曾被访问过，特附设一个 访问标志数组 visited，其初值均为 false，一旦某个顶点被访问，则其相应的分量被置为 true；
(2) 显然，过程 dfs是一个 递归过程 。但在遍历图时，对图中每一个未被访问过的顶点，仅调用一次 dfs过程，因为一旦它被访问过并作了标志，则不再从它出发进行搜索。因此，
遍历图的过程实际上是结每个顶点查找其邻接点的过程 ；
(3) 算法的时间复杂度取决于所采用的 存储结构 。在每次递归调用时，除了访问顶点及做标记外，主要的时间耗费在从该顶点出发搜索它的所有邻接点。
深度优先搜索（ DFS）遍历
图的遍历第七章 图第 44页用邻接矩阵表示图,dfs算法的时间复杂度是 O(n2)。这是因为搜索一个顶点的所有邻接点需花费 O(n)时间来检查矩阵相应行中所有的 n个元素，故从 n个顶点出发搜索所需时间是 O(n2)。
用邻接表表示图,搜索 n个顶点的所有邻接即为对各边表结点扫描一遍，故 dfs算法的时间复杂度为 O(n+e)，这里 n为图中顶点数
,e为无向图中边的数目或有向图中弧的数目；
(4) 算法的空间复杂度：所需用的辅助空间是标志数组和实现递归所用的栈。故它们的空间复杂度为 O(n)；
(5) 对于用邻接矩阵或邻接表作为存储结构时，其具体的 dfs算法，与采用的数据结构及存储结构有关，可在算法 7.4的基础上改造之；
(6) 若 G是 连通图,则从初始出发点开始的搜索过程结束也就意味着完成了对图 G的遍历。而若 G是 非连通图,则从图中任一顶点出发进行深度优先搜索不能访问到图中所有顶点。若从每个连通分量中都能先取一个顶点作为出发点进行搜索，便可访问到整个非连通所有顶点。（类似与森林的遍历）
算法分析第七章 图第 45页图的广度优先搜索（ Breadth-First search，简记为 BFS），它的遍历 类似于树的按层次遍历 。
算法思想,设给定图 G的初始状态是所有顶点均未曾被访问过
。 (1)在 G中任选一顶点 V0为初始出发点，则首先访问该出发点 V0，
并将其标记为已访问过,(2)接着依次访问 v0的所有邻接点
w1,w2,···,wt，然后,(3)再依次访问与 w1,w2,··,wt邻接的所有未曾访问过（每次访问某顶点，均作了标记）的顶点，依次类推，直至图中所有和初始出发点 v0有路径相通的顶点都已访问到为此。
若此时图中尚有未被访问的顶点 （在另一个连通子图中）,则选中这个未被访问的顶点，重复上述过程，直到图中所有顶点都被访问为止。
此算法的搜索次序体现了 优先朝横向发展 的趋势，故此搜索法被称之为广度优先搜索法。
广度优先搜索（ BFS）遍历
图的遍历第七章 图第 46页示例 4 无向图 G4及其广度优先搜索的过程
(a) 无向图 G4
图 7.13 遍历图的过程
(c) 广度优先搜索的过程所得的顶点访问序列为
V1→ V 2→ V 3→ V 4→ V 5→ V 6→V 7 →V 8
广度优先搜索（ BFS）遍历
图的遍历
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
1
V61 V7
73 6
V4 V5
V8 8
5
2 2
3
4
第七章 图第 47页在遍历过程中也需要一个访问标志数组。此外，为了顺次访问路径长度为 2,3,···的顶点，还需附设一个 队列 以存储已被访问的路径长度为 1,2,···的顶点。
void BFSTraver(Graph g,int visited[])
{ //对图 g按广度优先进行遍历
for( vi=1; vi <= vexnum; vi++ )
visited[vi] = false; //标志数组初始化
for( vi=1; vi <= vexnum; vi++ )
if( !visited[vi] )
bfs(g,vi) //调用从 vi出发广度优先遍历的递归过程
} //traver
算法 7.3
广度优先搜索（ BFS）遍历第七章 图第 48页
void bfs(Graph g,int v0 )
{ //从 vo出发广度优先遍历图 g
visite( v0 );
visited[v0] = true;
InitQueue( Q ); //初始化设置空队列 Q
EnQueue( Q,v0 ); //v0进队列 Q
while( !Empty( Q ))
{ v = DlQueue(Q); //队头元素 v出队列
w = FirstADJ(g,v); //求 v的邻接点
while( w≠0 )
{ if( !visited[w])
{ visite[w]; visited[w] = true;
EnQueue( Q,w )
};
w = NextADJ(g,v,w) //求下一邻接点
}
}
} //bfs 算法 7.5
时间复杂度与 dfs算法相同。区别仅在于对顶点，访问的顺序不同。
广度优先搜索（ BFS）遍历第七章 图第 49页对于无向图 G的遍历而言，
(1)若 G是 连通图,则从 G中任一顶点出发，仅需一次调用搜索过程（ dfs或 bfs），便可访问图中各个顶点
。
(2)若 G是 非连通图,则从 G中任一顶点出发，只能访问到初始出发点所在的连通分量中的所有顶点。
(3)若从每个连通分量中都选一个顶点作为初始出发点进行搜索，便可访问到整个非连通图，非连通图的遍历必须多次调用 dfs或 bfs算法。每次调用所得到的顶点访问序列恰为各个连通分量中的顶点集。
无向图的连通分量
图和连通性问题第七章 图第 50页示例 5 给定如下之无向图
G3及其邻接表
A B
L M
A
B
C
D
E
F
G
H
I
J
K
L
M
12 6 3 2 ∧
13 1 ∧
1 ∧
5 ∧
4 ∧
1 ∧
11 9 8 ∧
12 10 2 ∧
13 10 1 ∧
11 7 ∧
7 ∧
13 12 ∧
8 7 ∧
1
2
3
4
5
6
7
8
9
10
11
12
13
C D E
F G H
I J K
1 2
12 13
3 4 5
6 7 8
9 10 11
图 7.3 无向图 G3
图 7.14 G3的邻接表无向图的连通分量第七章 图第 51页对于如图 7.3所示的非连通无向图 G3，按照图 7.14所示 G3
的邻接表进行深度优先搜索遍历，分别从顶点 A,D和 G出发，
三次调用 dfs过程，可得到如下之顶点访问序列
ALMJBFC,DE,GKHI
由这三个顶点集分别加上所有依附于这些顶点的边，便构成了非连通无向图 G3的三个连通分量
A B
L M
C
F
J
D E
G H
I K
求非连通的连通分量的算法与 traver算法几乎完全一样，
只需在 dfs(g,vi)后增加 print过程，打印出有关顶点和边的信息
。
无向图的连通分量第七章 图第 52页在图论中，常常将树定义为一个 无回路连通图 。例如，下述两个图就是无回路连通图初看之下它们时不是树，但只要选定某个顶点做根，以树根为起点对每条边定向，就能将它们变为通常的树。
设 G=(V,E)是一个具有 n个顶点的连通图，则从 G中任一顶点出发作一次深度或广度优先搜索遍历图时，必将 E(G)分成两个集合
T(G)和 B(G),这里 T(G)是遍历该图时所通过的边集，则 B(G)是剩余的边集。今考虑图 G`=(V,T)。 由于 V(G`)=V(G),E(G`)=T<=E(G)
，则 G`是 G的子图，且形成包括 G所有顶点的一棵树,G`中的边构成该树的枝,称此树为 G的生成树 。
生成树
生成树第七章 图第 53页定义 1,一个连通图 G的子图如果是一棵包括 G的 所有顶点的树,则称该子图为 G的生成树（
Spanning Tree）。
推论,由于 n个顶点的连通图至少有 n-1条边，而所有包含 n-1条边及 n个顶点的连通图都是无回路的树,所以生成树是连通图的极小连通子图。
定义 2,由 dfs遍历所得到的生成树称为深度优先生成树；由 bfs遍历所得到的生成树称为广度优先生成树。
生成树
生成树第七章 图第 54页示例 6 无向连通图 G4
V1
V2 V3
V4 V5 V6 V7
V8
的深度优先生成树和广度优先生成树
G4的广度优先生成树注,虚线表示集合 B(G)中的边
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
V4
V8
V5
V6
V7
G4的深度优先生成树生成树第七章 图第 55页上面给出的生成树定义，是从连通图的观点出发，针对无向图而言的。由于从图的遍历可求得生成树,因此亦可从另一角度来定义生成 树 。
定义 3,若从图的某顶点出发，可以系统地访问遍图中的所有顶点，则遍历时经过的边和图的所有顶点所构成的子图，称作该图的生成树。
此定义不仅适用于无向图，对有向图同样适用
。显然，若 G是强连通的有向图，则从其中任一顶点 v出发，都可以访问遍 G中的所有顶点，从而得到以 v为根的生成树。若 G是有根的有向图，设根为 v
，则从根 v出发也可完成对 G的遍历，因此也能得到
G的以 v为根的生成树。
生成树第七章 图第 56页示例 7 有根的有向图及其 dfs生成树与 bfs生成树
V1
V2 V6
V4
V3
bfs生成树
V1
V2 V6
V3
V1
V2 V5
V3 V7
dfs生成树
V5
V7
V4
V6
V4 V5
V7
生成树第七章 图第 57页图的生成树 不是唯一 的，从不同的顶点出发进行遍历，可以得到不同的生成树。
对于非连通图，每个连通分量中的顶点集和遍历时走过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图的生成森林。
示例 6 无向图 G3及其深度优先生成森林
A B
L M
C D E
F G H
I J K
图 7.3 无向图 G3
A
L
J B
M
F C
D
E K
H
I
G
1
2 6 7
3
4 5
8
9
10
11 13
12
注,虚线为集合 B(G)中的边
G3的深度优先生成森林生成树第七章 图第 58页下面给出非连通图的深度优先生成森林的算法,设以孩子兄弟链表 作为生成森林的存储结构。
void dfs_forest(Graph g,Tree &root )
{ /*建立非连通图的深度优先森林的孩子兄弟链表,root为指向根结点的指针
，局部变量 q指向最后生成的结点 */
root = NULL; //初始化建空树
for( vi=1; vi <= vexnum; vi++ ) visited[vi]=false;
for( vi=1; vi <= vexnum; vi++ )
if( !visited[vi] )
{ p = new(TreeNode); p->data = vi;
p->fch = NULL; p->nsib = NULL; //建生成树的根结点
if( root == NULL ) root = p; //第一棵树的根
else q->nsib = p; //其他树的根
q = p;
dfs_tree(g,vi,p) //建以 p为根的生成树
}
} //dfs_forest 算 法 7.6
生成树第七章 图第 59页
void dfs_tree(Graph g,int vo,Tree &p )
{ /*从 vo出发深度优先搜索图 g，建以 p↑为根的生成树的孩子兄弟链表，局部变量 q指向最后生成的结点，局部变量 false*/
visited[vo]=true;
w = FirstADJ(g,vo); first=true; //w为图 g中 vo的第一个邻接点
while( w≠0 )
{if( !visited[w] )
{ if( first ) //把 第一个邻接点作为长子
{ p->fch = new(TreeNode); q=p->fch; first=false }
else
{ q->nsib = new(TreeNode);
q = q->nsib; //建生成树的一条边
}
q->data = w; q->fch = NULL; q->nsib = NULL;
dfs_tree(g,w,q); //从 w出发深度优先搜索图 g，
建以 q为根的生成树
}
w = NextADJ (g,vo,w);
} //while
} //dfs_tree 算 法 7.7
生成树第七章 图第 60页对于网络 G=(V,E)，边是带权的,因而 G的生成树的各边也是带权的。
定义 4,称由网 G=(V,E)所产生的生成树各边的权值总和为该生成树的权，并称权最小的生成树为网 G的最小生成树（
Minimum Spanning Tree）。
生成树和最小生成树有许多重要的应用。令图 G的顶点表示城市，边表示连接两个城市之间的通信线路。 n个城市之间最多可设立的线路共有 n(n-1)/2条，而把 n个城市连接起来至少要有 n-1条线路。因此，图的生成树表示了建立通信网的可行方案。
假设给图中的边都赋予权，而这些权可表示两上城市之间的通信线路的长度或建造代价。
最小生成树
最小生成树第七章 图第 61页构造连通网的最小（代价）生成树 (minumum-cost
spanning tree或 MST)的两个算法,普里姆（ Prim） 算法 和 克鲁斯卡尔 Kruskal算法 。
给定一个连通无向图 G,且它的每条边均有相应的长度或权值，则 MST是一个包括 G的所有顶点及其边子集的图,边的子集满足下列 条件,
(1) 这个子集中所有边的权之和为所有 边子集 中最小的 ；
(2) 子集中的边能够保证图是 连通 。
最小生成树
最小生成树第七章 图第 62页示例 8 一个图及其 MST。
● 所有的线都是原图的边,MST中边的子集用粗线（兰色）表示
●如果用边（ D,F）代替边（ C，
F），可得到另一个 MST。
A
B
E
F
C
D
7 5
2 69
1
1
2
最小生成树
MST的性质,假设 N=（ V,{E}） 是一个连通图,U是 V的非空子集。
若?e=(x,y)，其权重最小，且 x ∈ U,y∈ V-U
则一定存在一棵包含边 e的最小生成树。
第七章 图第 63页
Prim 算法利用 MST 性质来构造连通网的最小生成树。它 着眼于顶点的处理 。
算法思想：设 N=(V,E)是连通网。为简化用序号 1
至 n来表示顶点集合，则 V={1,2,··,n}。设所求的最小生成树为 T=(V,TE)，其中 V是 T的顶点集,TE是 T的边集。将 N中边上的权看作是长度。 Prim 算法思想的执行步骤如下：
(1)初始化：令 U={u0} (u0∈ V),TE=? ;
(2)在所有 x∈ U,y∈ V-U的边 (x,y) ∈ E中找一条代价最小的边 (x0,y0)并入集合 TE,同时 y0并入 U；
(3) 重复 (2)，直至 U=V时为止。
此时 TE中必有 n-1条边，且 T=(V,TE)为 N的最小生成树 。
构造最小生成 树的 Prim 算法第七章 图第 64页示例 9 设有如下之连通网 N1
今欲使用 Prim算法构造连通网 N1的最小生树。
1
3
2 4
5 6
56
5
3 6 4 2
6
51
其权重矩阵为
∞ 6 1 5 ∞ ∞
6 ∞ 5 ∞ 3 ∞
1 5 ∞ 5 6 4
5 ∞ 5 ∞ ∞ 2
∞ 3 6 ∞ ∞ 6
∞ ∞ 4 2 6 ∞
A=
构造最小生成 树的 Prim 算法
[分析 ] 先采用图示法，然后写出 Prim算法。
初始化 令 u0=1，即 u={1},
设置一辅助数组 Closedge[vtxptr],域 lowcost、域 vex
域 lowcost,记录每个顶点 v ∈ V-U，到 U集的最小代价域 vex,记录 该边在 U集中的顶点第七章 图第 65页
v
c l a se d g e
2 3 4 5 6 U V - U
v e x
l o w c o st
①
6
①
1
①
5
①
∞
①
∞
{ 1 } { 2,3,4,5,6 }
i = 1,k = 3
输出 1 3
v e x
l o w c o st
③
5 0
①
5
③
6
③
4
{ 1,3 } { 2,4,5,6 }
i = 2,k = 6
输出 3 6
v e x
l o w c o st
③
5 0
⑥
2
③
6 0
{ 1,3,6 } { 2,4,5 }
i = 3,k = 4
输出 6 4
v e x
l o w c o st
③
5 0 0
③
6 0
{ 1,3,6,4 } { 2,5 }
i = 4,k = 2
输出 3 2
v e x
l o w c o st 0 0 0
②
3 0
{ 1,3,6,4,2 } { 5 }
i = 5,k = 5
输出 2 5
v e x
l o w c o st 0 0 0 0 0
{ 1,3,6,4,2,5 }
图 7.17 构造最小生成树过程中辅助数组中各分量的值
∞ 6 1 5 ∞ ∞
6 ∞ 5 ∞ 3 ∞
1 5 ∞ 5 6 4
5 ∞ 5 ∞ ∞ 2
∞ 3 6 ∞ ∞ 6
∞ ∞ 4 2 6 ∞
A=
1
3
2 4
5 6
56
5
3 6 4 2
6
51
第七章 图第 66页
void MiniSpanTree_PRIM( Mgraph g,VertexType u )
{ //从 uo出发构造网 gn的最小生成树,按 Prim算法输出生成树上各条边
k = LocateVex( g,u );
for( j = 1; j <= g.vernum; j++ )
if( j!=k )closedge[j] = {u,g.arcs[k][j].adj}; //辅助数组初始化
closedge[k].lowcost = 0; //lowcost值为 0说明并入顶点集 U
for( v = 1; v < g.vexnum,v++ )
{ k = minimum(closedge); //lowcost值为 0的数组元素不参与取最小值运算
printf( closedge[k].adjvex,g.vex[k] ); //输出生成树的边
closedge[k].lowcost = 0; //顶点 k并入 U集
for( j = 1; j <= g.vexnum; j++ )
if( g.arcs[k][j].adj ＜ closedge[j].lowcost )
{ closedge[j].lowcost = { g.vexs[k],g.arcs[k][j].adj }
//在新的顶点并入 U之后，重新选择具有最小代价的边
}
} //minispantree_PRIM 算 法 7.8
Prim 算法算法分析：时间复杂度 O(n2)，其中 n为连通网 N的顶点数。
第七章 图第 67页构造最小生成树的 Kruskal 算法克鲁斯卡尔 (Kruskal) 算法亦是利用 MST性质来构造连通网的最小生成树，但它 着眼于边的处理 。
算法思想,按权值递增的顺序来构造最小生成树 。 设
N=(V,E)是连通网，而所求最小生成树为 T=(V,TE)，其中 V是顶点集,TE是 T的边集。将 N中边上的权看作是长度。 Kruskal算法的执行步骤如下：
(1) 初始化,令 T=(V,?)(即 TE=?)为只有 n个顶点而无边的非连通图，图中每个顶点自成一个连通分量；
(2) 在 E中选取一条代价最小的边 (u,v)，若该边依附的顶点 u,v落在
T中不同的连通分量上（使该边加入 T中后不能形成回路），则将此边加入到 TE中，并在 E中删除该边，否则舍去选择下一条边；
(3) 重复 (2)，直至 T中所有顶点都在同一连通分量上时为止。
第七章 图第 68页示例 10 设连通网 N1如示例 2，今按 Kruskal 算法思想用图示法构造出一棵最小生成树：
(1) 初始化,TE=? ；
1
3
2 4
5 6
56
5
3 6 4 2
6
51
1
3
2 4
5 6
构造最小生成树的 Kruskal 算法第七章 图第 69页
Kruskal 算法的粗略描述
void MiniSpanTree_KRUSKAL( )
{ TE =?;
while( TE中少于 n-1条边 )
{ 从 E(N)中选取一条具有最小权值的边 (v,w)；
从 E(N)中删去边 (v,w)；
if( 边 (v,w)加入到 T中不能形成回路 )
将边 (v,w)加入到 TE中 ;
}
} //minispantree_KRUSKAL
算法分析：时间复杂度 O(eloge)，其中 e为连通网 N的边数。
注,Kruskal 算法的时间复杂度仅与网中边数有关，而与顶点 数无关，故相对于 Prim算法而言，适合于求边稀疏的网的最小生成树。
构造最小生成树的 Kruskal 算法第七章 图第 70页示例 11 设有如下之连通网 N2
执行 Kruskal 算法的过程如下（简化形式）初始状态
1 2
5 4
6 3
16
18
21
33
11
14 619
6
5
1 2
5 4
6 3
构造最小生成树的 Kruskal 算法第七章 图第 71页定义,一个无环的有向图称做有向无环图 (Directed Acycline Graph),简称 DAG 图。
示例 12 比较下列树、图图 7.21 有向树,DAG 图和有向图（有环）一例
DAG 图是一类较有向树更一般的特殊有向图。它是描述含有公共
（共享）子式的表达式的有效工具，也是描述一个工程项目（
Project）是否能顺利进行以及估算整个工程项目完成所必须的最短时间等方面应用的有效工具。
有 向 无 环 图第七章 图第 72页示例 12 下述表达式
((a＋ b)× (b× (c＋ d))＋ (c＋ d)× e)× ((c＋ d)× e) (△ )
可分别用 二叉树 及 有向无环图 描述如下图 7.22 用二叉树描述表达式 (△ )
＋
a b
×
＋
b c d
＋ c d
＋
e×
＋
× e
×
c d
×
×
＋×
＋
a b
×
ec d× ＋ 图 7.23 描述表达式 (△ )的有向无环图
有 向 无 环 图第七章 图第 73页术语与概念定义 1 （ AOV-网） 若在有向图 G 中，用顶点表示活动或任务
，用弧（有向边）表示活动或任务间的优先关系，则称此有向图为顶点表示活动的网 （ Activity on vertex network），简称 AOV-网。
在 AOV-网 中，若从顶点 i 到顶点 j 有一条有向路径，则 i 是 j
的前驱,j 是 i 的后继。若 <i,j> 是网中一条弧，则 i 是 j 的直接前驱,j 是 i 的直接后继。
定义 2 （偏序与全序） 若集合 X 上的关系 R是自反的、反对称的和传递的，则称 R 是集合 X 上的偏序 (Partial Order)关系 ；
设 R 是集合 X 上的偏序，如果对 每个 x,y∈ X,必有 xRy 或 yRx，
则称 R 是集合 X 上的全序（ Full Order）关系。
拓 扑 排 序第七章 图第 74页示例 13 下述两个有向图图 7.25 表示偏序和全序的有向图图中弧 <x,y> 表示 x≤y。则 (a) 表示偏序,(b) 表示全序。偏序指集合 仅有部分成员之间可以比较,而 全序指集合中全体成员之间均可比较 。
定义 3 （拓扑排序） 由某个集合上的一个偏序得到该集合上的一个全序的操作称为拓扑排序（ Topological Sort）,
比如，在图 7.25(a) 中的有向图上增加一个表示 2≤3 的弧，则 (a) 表示的亦为全序，且称此全序为 拓扑有序 （ Topological Order），而由偏序定义得到拓扑有序的操作便是拓扑排序。
2
3
41 2 3 41
(b)(a)
拓 扑 排 序第七章 图第 75页拓扑排序的方法拓扑排序的简洁描述,将一个 有向无环图 （ DAG）中所有顶点在不违反先决条件规定的基础上排成线性序列的过程称为拓扑排序 。
示例 14 AOV-网的“死锁”现象
V2
V3
V1
V4 V5
V6
注,并非任何 AOV-网的顶点都可以排成拓扑有序序列。
若网中存在回路，则将找不到该网的拓扑有序序列 。
可以通过拓扑排序来检查 AOV-网中有无回路存在。
第七章 图第 76页任一个无回路的 AOV-网，其顶点都可以排成一个拓扑有序序列，并且其拓扑有序序列不一定是唯一的 。
对一个 AOV-网进行拓扑排序的基本步骤：
(1) 在有向图中选择一个 没有前驱的顶点 并输入之；
(2) 在图中删除该顶点和所有以它为尾的弧 ；
(3) 重复上述步骤，直至 全部顶点均已输出 或者 当前图中不存在无前驱的顶点为止 。
前者说明方案可行，而后者说明该有向图中存在回路即环。
拓扑排序的方法
V2
V3
V1
V4 V5
V6
V2
V3
V1
V4 V5
V6
第七章 图第 77页示例 15 下述有向图的一种拓扑有序序列产生过程
V1 V2
V4 V3
V6 V5
(a) AOV-网图 7.28 AOV-网及其拓扑有序序列产生的过程拓扑排序的方法
V1 V2
V4 V3
V6 V5
V1— V3— V2 — V6— V4— V5
AOV-网 存储结构的选择 可采用邻接表结构
V1 0 4 3 2 ∧
firstarc
vexdat indegree adjvex nextarc
如果在邻接表的表头结点中增加一个计数域，它记录该顶点的直接前驱结点的数目，也就是它的入度第七章 图第 78页示例 16 图 7.28(a)的有向图的邻接表
V1 V2
V4 V3
V6 V5
V1 0
V2 2 ∧
V3 1
V4 2
V5 3 ∧
V6 0
4 3 2 ∧
5 2 ∧
5 4 ∧
5 ∧
1
2
3
4
5
6
vexdat indegreefirstarcadjvexnextarc
图 7.29(a) 图 7.28(a)的有向图的邻接表顶点表 边表拓扑排序的方法第七章 图第 79页入度 indegree 域在输入时建立。每当输入一条边 <vi,vj>时
，顶点 vj的 indegree 域就增加 1。
另外，在拓扑排序过程中，当某顶点的表头结点中 indegree
域变成 0 时，需将该顶点输出，同时将该顶点的直接后继顶点的表头结点中 indegree 域减去 1。
由于入度为零的顶点在拓扑有序序列中的次序是人为地设定的
，为了方便其见，可以设置一个栈存放入度为零的顶点，每当输出便从栈中删除；反之，当出现新的入度为零的顶点则可入栈。
拓扑排序的方法第七章 图第 80页示例 13 链栈 top和 indegree 链域的变化情况模拟。 初始
V1 0
V2 2 ∧
V3 1
V4 2
V5 3 ∧
V6 0
4 3 2 ∧
5 2 ∧
5 4 ∧
5 ∧
1
2
3
4
5
6
6 1 ∧top
取走 V6 后 取走 V1 后 取走 V3 后
1 ∧top
V1 0
V2 2
V3 1
V4 1
V5 2
V6 0
2top 4 ∧
V1 0
V2 0
V3 0
V4 0
V5 1
V6 0
3top 4 ∧
V1 0
V2 1
V3 0
V4 0
V5 2
V6 0
拓扑排序的方法第七章 图第 81页示例 13 链栈 top和 indegree 链域的变化情况模拟。
初始
V1 0
V2 2 ∧
V3 1
V4 2
V5 3 ∧
V6 0
4 3 2 ∧
5 2 ∧
5 4 ∧
5 ∧
1
2
3
4
5
6
6 1 ∧top
取走 V2 后 取走 V4 后 取走 V5 后
V1 0
V2 0
V3 0
V4 0
V5 1
V6 0
top 4 ∧
取走 V3 后
2top 4 ∧
V1 0
V2 0
V3 0
V4 0
V5 1
V6 0
V1 0
V2 0
V3 0
V4 0
V5 0
V6 0
top 5 ∧ top
V6— V1— V3— V2— V4— V5
第七章 图第 82页拓扑排序算法设有向图的邻接表类型定义如下
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct VNode{
VertexType data;
int InDegree;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
第七章 图第 83页拓扑排序算法描述
Status toposort( ALGraph g )
{
FindInDegree( g ); //求各节点入度 indegree[1..vexnum]
InitStack( s );
for( i = 1; i <= g.vexnum; i++ ) //建立入度为 0的顶点的栈
if( g.vertices[i].InDegree == 0 ) Push( s,i );
count = 0;
while( !StackEmpty( s ))
{
Pop( s,i );
printf( i,g.vertices[i].data ); //输入并计数
count++;
for( p = g.vertices[i].firstarc; p; p=p->nextarc )
{ k = p->adjvex; //每个邻接点入度减 1
if( !( --g.vertices[k].InDegree )) Push( s,k );
//入度为 0，入栈
} //for
} //while
if( count < g.vexnum ) return ERROR; //有回路
return OK;
}
拓扑排序算法第七章 图第 84页关键路径术语与概念
AOE-网 若在带权有向图 G 中,顶点表示事件,有向边表示活动,权表示活动持续的时间,则称此有向图 G 为边表示活动的网（ Activity On Edge network），简称 AOE-网。
在 AOE-网中，事件与活动之间的关系：
由一个顶点发出的边所表示的所有活动，直到这个顶点所表示的事件已经发生了，才能开始。而仅当进入到这个顶点的所有边表示的活动已经完成时，该点表示的事件才能开始。
通常可用 AOE-网来研究下列问题：
1、估算工程计划的完成时间。
2、哪些活动是影响工程进度的关键表示实际工程计划的 AOE-网，应该是 无回路 的，
并且网中只有一个入度为零的顶点（ 称为源点），
也只有一个出度为零的顶点（ 称为汇点）。
第七章 图第 85页示例 19 下述 AOE-网包含 9个事件 V1,V2,···,V9，
11个活动 a1,a2,···,a11，所对应的 11个权值分别为 6,4,5,1，
1,2,9,7,4,2,4。
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
图 7.31 一个 AOE-网关键路径假定上述 AOE-网表示一个工程项目的计划。那么,事件 V1 表示整个工程开始,V9 表示整个工程结束 。事件 V5 表示活动 a4和 a5已完成，活动 a7 和 a8 可以开始。权值表示完成相应活动所需天数。
问题
(1) 完成整个工程项目至少需要多少天？
(2) 哪些活动是影响工程进度的关键？
第七章 图第 86页活动的最迟开始时间 在不推迟整个工程项目完成的 前提 下，
活动 ai 最迟必须开始进行的时间称为活动 ai 的最迟开始时间，以
l(i)表示之。
活动的时间余量 令 l(i)－ e(i) 为活动 ai 完成的时间余量。
关键活动 满足 e(i)=l(i) 的活动称为关键活动。故，关键路径上的所有活动都是关键活动。
关键路径关键路径 路径 长度最长 的路径称为关键路径（ Critical Path）。
关键路径定义了完成一个工程项目所需的最少时间,即从源点到汇点所需最长的活动持续时间之和。
活动的最早开始时间 事件 Vi 能发生的最早时间为从源点 V1 到顶点 Vi 的最长路径长，它决定了由该顶点表示的事件为尾的所有边即活动的最早开始时间。以 e(i) 表示活动 ai 的最早开始时间。
第七章 图第 87页关键路径为 V1— V2— V5— V7— V9 或者 V1— V2— V5— V8— V9
故 V9 的最早发生的时间是 18(天 )，即该工程需要 18天完成。
注,一个 AOE-网可能有多条关键路径。
示例 19 下述 AOE-网
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9图 7.31 一个 AOE-网关键路径活动 a6 的最早开始时间 e(6)=5，而最迟开始时间 l(6)=18－ 4－
4－ 2=8。
这意味着,活动 a6 推迟 3天开始或者延迟 3天完成，都不会影响整个工程项目的完成。
又,e(7)=e(8)=6+1=7,l(7)= 18－ 2－ 9=7,l(8)=18－ 4－ 7=7，即
e(7)=l(7),e(8)=l(8)。这表明,活动 a7 与 a8 的最早开始时间与最迟开始时间相同，从而 a7 与 a8 的时间余量均为 0。
第七章 图第 88页事件的最早发生时间 若活动 ai 由弧 <j,k> 表示，则从源点 V1 到顶点 Vj 的最长路径长度称为事件 Vj 的最早发生时间，
记作 ve(j)。 显然地，有 e(i) = ve(j)。
关键路径
(7-1)
事件的最迟发生时间 若活动 ai 由弧 <j,k> 表示，则称事件 Vj 最迟必须发生的时间为事件 Vj 的最迟发生时间，记作 vl(j)。
假定活动 ai 的持续时间记为 dut(<j,k>)，则有
l(i)=vl(k)－ dut(<j,k>).
综上所述,若设活动 ai 由弧 <j,k> 表示，其持续时间为
dut(<j,k>)，则有
e(i)=ve(j)
l(i)=vl(k)－ dut(<j,k>)
VkVj aidut(<j,k>)
第七章 图第 89页求事件 /活动的最早发生 /开始时间和最迟发生 /开始时间由 (7-1)，有
e(i)=ve(j)
l(i)=vl(k)－ dut(<j,k>)
其中假定活动 ai 由弧 <j,k> 表示，其持续时间为 dut(<j,k>)。
(7-1)
(1) 求 ve( j)
为求 ve(j)，从源点 V1开始，自左至右对每个事件向前计算，直至计算到汇点 Vn 为止。对于事件 Vj，仅当其所有前趋事件 Vi 均已发生且所有由边 <Vi,Vj> 表示的活动均已完成时才有可能发生。因此，有
ve(1)=0
ve(j)=Max{ve(i)+dut(<i,j>)}
i <i,j>∈ T,2≤j≤n
其中 T 是所有以 Vj 为头的弧的集合。
(7-2)
今欲推出求 事件的最早发生时间 ve 和最迟发生时间 vl 的计算公式求 ve(j) 和 vl(j) 需分向前阶段和后阶段递推地进行计算第七章 图第 90页
V1
V2a1
V3
V5
ve(1)=0,
a2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
示例 20 对于如图 AOE-网，
求各个事件的 ve。
关键路径上述计算顺序是按顶点的某一拓扑有序序列的次序进行的。
ve(2)=ve(1)＋ dut(<1,2>)＝ 0＋ 6=6,
ve(3)=ve(1)＋ dut(<1,3>)＝ 0＋ 4=4,
ve(4)=ve(1)＋ dut(<1,4>)＝ 0＋ 5=5,
ve(5)=Max{ve(2)＋ dut(<2,5>),ve(3)＋ dut(<3,5>)}=Max{6＋ 1,4＋ 1}=7,
5
ve(6)=ve(4)＋ dut(<4,6>)＝ 5＋ 2=7,
ve(7)=ve(5)＋ dut(<5,7>)＝ 7＋ 9=16,
ve(8)=Max{ve(5)＋ dut(<5,8>),ve(6)＋ dut(<6,8>)}=Max{7＋ 7,7＋ 4}=14,
ve(9)=Max{ve(7)＋ dut(<7,9>),ve(8)＋ dut(<8,9>)}
=Max{16＋ 2,14＋ 4}=18,
第七章 图第 91页
(2) 求 vl(j)
为求 vl(j)，从汇点 Vn开始，从右到左逐个事件 逆推 计算，
直到计算到源点 V1 时为止。为了尽量缩短工程的工期，通常把汇点事件 Vn 的最早发生时间（即工程的最早完工时间）作为 Vn
的最迟生时间。
不难推断,事件 Vj 的最迟发生时间 vl(j) 是其所有后继事件 Vk 的最迟发生时间 vl(k)与活动 <vj,vk> 的持续时间之差中的最小者，
则有
vl(n)=ve(n)
ve(j)=Min{vl(k)－ dut(<j,k>)}
k <j,k>∈ S,1≤j≤n－ 1
其中 S 是所有以 Vj 为尾的弧的集合。
(7-3)
关键路径第七章 图第 92页
vl(9)=ve(9)＝ 18,
vl(8)=vl(9)－ dut(<8,9>)＝ 18－ 4=14,
vl(7)=vl(9)－ dut(<7,9>)＝ 18－ 2=16,
vl(6)=vl(8)－ dut(<6,8>)＝ 14－ 4=10,
vl(5)=Min{vl(8)－ dut(<5,8>),vl(7)－ dut(<5,7>)}
=Min{14－ 7,16－ 9}=7,
vl(4)=vl(6)－ dut(<4,6>)＝ 10－ 2=8,
vl(3)=vl(5)－ dut(<3,5>)＝ 7－ 1=6,
vl(2)=vl(5)－ dut(<2,5>)＝ 7－ 1=6,
vl(1)=Min{vl(4)－ dut(<1,4>),vl(3)－ dut(<1,3>)
vl(2)－ dut(<1,2>}=Min{8－ 5,6－ 4,6－ 6} =0.
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
示例 21 对于如图 AOE-网，
求各个事件的 vl。
关键路径上述计算顺序是按顶点的某一拓扑有序序列的 逆序 进行的。
第七章 图第 93页示例 22 利用公式 (7-2),(7-3)以及 (7-1)可相继求得诸事件的最早、最迟开始时间，从而找出该 AOE— 网的诸关键活动并确定关键路径。对于示例 1中的 AOE— 网，可列表示如下事件 V 1 V 2 V 3 V 4 V 5 V 6 V 7 V 8 V 9
ve 0 6 4 5 7 7 16 14 18
vl 0 6 6 8 7 10 16 14 18
活动 a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a 10 a 11
e 0 0 0 6 4 5 7 7 7 16 14
l 0 2 3 6 6 8 7 7 10 16 14
l - e 0 2 3 0 2 3 0 0 3 0 0
由此可得所给 AOE— 网的关键路径如下图所示（红色与兰色）
V1
V2
V5
V7
V9
V8
a1 a4
a8 a11
a10a7
2
4
9
7
16
关键路径第七章 图第 94页分析：
(1) 并非加快任何一个关键活动都可以缩短整个工程的工期，只有加快包括在 所有关键路径上 的关键活动才能达到此目的。 例如，若将 a11由 4天改为
3天，并不能使整个工期由 18天变为 17天，但若使 a1由 6天改为
4天，则整个工期可缩短至 16天；
V2a1
V3
V5V1 a
2 a5
a4
4 1
16
V7a
7
V8
V9a8 a11
a10
7 4
29
V4 V6
5
2
4a3 a
6
a9
关键路径
(2) 关键路径是要以变化的，提高某些关键活动的速度，有可能使原先的非关键路径变为新的关键路径，因而关键活动的速度提高是有限度的。
比如，若将 a1由 6天改成 4天，则 a2和 a5成为关键路径。如果再减 …
第七章 图第 95页上述两个计算 ve(j)和 vl(j)的递推公式必须分别在拓扑有序和逆拓扑有序的前提下进行，
即：
ve(j)必须在 Vj的所有前驱的最早发生时间求得之后才能确定，
vl(j)则必须在 Vj有所有后继的最迟发生时间求得之后才能确定。
因此，可以在拓扑排序的基础上计算 ve(j)和 vl(j)。
求关键路径的算法第七章 图第 96页求关键路径的算法求关键路径的算法思想如下：
(1) 输入 e 条弧 <j,k>，建立 AOE— 网的存储结构 — 邻接表
（这里，求关键路径与拓扑排序有紧密关系）；
(2) 从源点 V1出发，令 ve[1]=0，按拓扑有序求其余各顶点的最早发生时间 ve[j](2≤j≤n)。若网中不存在环（即回路），
则继续执行 (3)；
(3) 从汇点 Vn出发，令 vl[n]=ve[n]，按逆拓扑有序求其余各顶点的最迟发生时间 vl[j](1≤j ≤n-1)；
(4) 根据各顶点的 ve和 vl值及公式 (7-1)，
求每条弧 s的 e(s)和 l(s)。若 e(s)=l(s)，则为关键活动。
第七章 图第 97页算法说明
(1) 求 ve[k]
计算各顶点的 ve值是在拓扑排序的过程中进行的，故需对原拓扑排序算法作如下修改
a.在拓扑排序之前设初值，即令 ve[i]=0(1 ≤i ≤n);
b.在算法 中增加一个计算 Vj直接后继 Vk的最早发生时间
ve[k]的操作
if( ve[j] + dut(<j,k>) > ve[k] )
ve[k] = ve[j] + dut(<j,k>);
求关键路径的算法
(2) 求 vl[k]
为能按逆 拓 扑有序序列的顺序计算各顶点的 vl值，需记下在拓扑排序过程中求得的拓扑有序序列。故需在算法中增设一个栈以记录拓扑有序序列 ;
第七章 图第 98页修正的拓扑排序算法描述
Status toposort( ALGraph g,Stack &T )
{
FindInDegree( g,indegree ); //求各节点入度 indegree[1..vexnum]
InitStack( T ); InitStack( s ); count = 0;
ve[1..g.vexnum-1] = 0;
for( i = 1; i <= g.vexnum; i++ ) //建立入度为 0的顶点的栈
if( !indegree[i] ) Push( s,i );
count = 0;
while( !StackEmpty( s ))
{
Pop( s,j ); Push( T,j ); count++;
for( p = g.vertices[i].firstarc; p; p=p->nextarc )
{ k = p->adjvex; //每个邻接点入度减 1
if( !( --indegree[k])) Push( s,k ); //入度为 0，入栈
if( ve[j] + *(p->info) > ve[k] )
ve[k] = ve[j] + *(p->info);
} //for
} //while
if( count < g.vexnum ) return ERROR; //有回路
return OK;
} //算法 7.13
第七章 图第 99页求关键路径算法描述
Status critical_path( ALGraph G )
{ //G为有向图 输出该有向图中各项关键活动
if( !TopoSort( G,T )) return ERROR;
j = T.Top(); vl[1..G.vexnum] = ve[j]; //初始化
while( !StackEmpty( T )){ //按逆拓扑序求各顶点 vl
for( Pop(T,j),p=G.vertices[j].firstarc; p; p=p->next )
{ k = p->adjvex; dut = *(p->info);
if( vl[k] – dut < vl[j] ) vl[j] = vl[k] – dut;
}
for( j = 1; j < G.vexnum; j++ ) //求 ee,el和关键活动
for( p = G.vertices[j]; p; p->nextarc )
{ k = p->adjvex; dut=*(p->info);
ee = ve[j]; el = vl[k] – dut;
tag = ( ee == el )? ‘*’,‘’;
printf( j,k,dut,ee,el,tag ); //输出
}
}
求关键路径的算法算法分析：这两种算法的时间复杂度均为 O(n+e)；计算弧的活动最早开始时间 ee和最迟开始时间 el的时间复杂度为 O(e)；总的求关键路径的时间复杂度为 O(n+e)。
第七章 图第 100页示例 23 给定如下之 AOE— 网
V1
V2
V4
V5
V6
a1 a3
a7
a7
1
2
23
V3
2a2 a64
a5
3
a4
3 a
8
图 7.32 AOE— 网求关键路径的算法
1、若弧按逆时针方向编号，求依算法 7.13的拓扑排序序列，及各事件的最早发生时间；
2、根据逆拓扑排序序列，求各事件的最迟发生时间；
3、指出网中的所有关键路径。
解,1、拓扑排序序列，及各事件的最早发生时间；
V1 0,3,2,0,0,0 top1 V3V2
V2 0,3,2,5,6,0 top1 V5 V3
V5 0,3,2,5,6,7 top1 V3
第七章 图第 101页
V1
V2
V4
V5
V6
a1 a3
a7
a7
1
2
23
V3
2a2 a64
a5
3
a4
3 a
8
图 7.32 AOE— 网
V5 0,3,2,5,6,7 top1 V3
V3 0,3,2,6,6,7 top1 V4
V4 0,3,2,6,6,8 top1 V6
V6 0,3,2,6,6,8 top1
求关键路径的算法
V1 V2 V5 V3 V4 V6
第七章 图第 102页
V1
V2
V4
V5
V6
a1 a3
a7
a7
1
2
23
V3
2a2 a64
a5
3
a4
3 a
8
图 7.32 AOE— 网
ve,0,3,2,6,6,8
求关键路径的算法
V1 V2 V5 V3 V4 V6
2、根据逆拓扑排序序列，求各事件的最迟发生时间；
V6
8
V4
6
V3
2
V5
7
V2
4
V1
0
vl,0,4,2,6,7,8
3,根据公式 (7-1)求 ee,el
由 ee=el求关键活动。
V1,V3,V4,V6
第七章 图第 103页问题的提出交通网络中常常提出这样的问题：两地之间是否有路相连？在有多条通路的情况下，哪一条路最短？
从城 A到城 B若无直达车，则亦需选择一条途中中转次数最少的路线。
交通网络可用带权图表示，其中权值或表示城镇间的距离，
或是交通费用，或是所需时间、速度等等。
讨论带权有向图，并称路径上的第一个顶点为 源点 (Source),
最后一个顶点为 终点 (Destination)。
两种常见的最短路径问题
1,单源点的最短路径问题
2,所有顶点对之间的最短路径问题。
这里路径长度的度量是路径上边的权值之和。
最 短 路 径第七章 图第 104页单源点的最短路径问题问题：对于给定的带权有向图（有向网） D=（ V,E）和源点 v，
求从 v到 D中其余各顶点的最短路径。
示例 24 有如下之有向网 D1，其中边上各数值是边的权值，则可列表给出人始点 V0到各顶点之间的最短路径
V5
V4
V3V2
V1
V0
5
100 60
20
50
10
30
10
始点 终点 最短路径 路径长度
V0 V1 无
V2 (V0,V2) 10
V3 (V0,V4,V3) 50
V4 (V0,V4) 30
V5 (V0,V4,V3,V5) 60
第七章 图第 105页按路径长度 递增的次序 产生最短路径的 Dijkstra算法有向图 D1的按路径长度递增的次序排列的一张最短路径表
V5
V4
V3V2
V1
V0
5
始点 终点 最短路径 路径长度
V0 V1 无
V2 (V0,V2) 10
V4 (V0,V4) 30
V3 (V0,V4,V3) 50
V5 (V0,V4,V3,V5) 60
10
30
50
60
100 60
30
2010
50
10
第七章 图第 106页集合 S,表示已求得最短路径的终点的集合。 S的初态为 S=? 。
集合 V-S,尚未确定最短路径的顶点集合。
辅助向量 dist：其分量 D[i]表示当前所找到的从始点 v到终点 Vi的最短路径的长度。 dist[i]的初态为
arcs(v,vi)，若 <v,vi>∈ E
D[i] =
+∞,否则从始点 v出发的长度最短的一条 最短 路径：
D[j]=Min{D[i]| vi ∈ V}
此路径为 v到 vj。可把顶点 Vj加入到 S中。
下一条长度 次短 的最短路径：设终点是 Vk，则此路径或者是 v-vk，
或者 v-vj-vk。将 vk亦加入到 S中。
一般情况下，有,下一条最短路径（设其终点为 x）或者是 v-x
，或者是中间只经过 S中的顶点而最后到达顶点 x的路径 。
按路径长度 递增的次序 产生最短路径的 Dijkstra算法第七章 图第 107页
Dijkstra 算法思想
(1) 邻接矩阵 arcs来表示带权有向图，若 <vi,vj>不存在，则置
arcs[i,j] 为 ∞。 S为已找到从 v出发的最短路径的终点的集合，它的 初始状态为空集 。 D[i]的初态为
arcs(v,vi)，若 <v,vi>∈ E
D[i]=
+∞,否则
(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] k? V-S
则修改 dist[k]为 D[k] = D[j]+arcs[j][k]
(4) 重复操作 (2),(3)共 n-1次。由此求得从 v到图上其余各顶点的最短路径是依路径长度递增的序列。
按路径长度 递增的次序 产生最短路径的 Dijkstra算法第七章 图第 108页示例 25 有向网 D1及其带权邻接矩阵为有向图 D1
∞ ∞ 10 ∞ 30 100
∞ ∞ 5 ∞ ∞ ∞
∞ ∞ ∞ 50 ∞ ∞
∞ ∞ ∞ ∞ ∞ 10
∞ ∞ ∞ 20 ∞ 60
∞ ∞ ∞ ∞ ∞ ∞
按 Dijkstra算法，可列表表示从源点 V0到其余各顶点的最短路径，以及运算过程中
arcs向量的变化：
终点 从 v 0 到各终点的 d i s t 值和最短路径
V 1 ∞ ∞ ∞ ∞ ∞无
V 2
10
V 0 - V 2
V 3 ∞
6 0
V 0 - V 2 - V 3
5 0
V 0 - V 4 - V 3
V 4
30
V 0 - V 4
30
V 0 - V 4
V 5
10 0
V 0 - V 5
10 0
V 0 - V 5
9 0
V 0 - V 4 - V 5
6 0
V 0 - V 4 - V 3 - V 5
V j V 2 V 4 V 3 V 5
V5
V4
V3V2
V1
V0
5
100 60
20
50
10
30
10
第七章 图第 109页
void shortpath_DIJ( Mgraph G,int v0,ShortPathTable &D)
{
for( v = 1; v <= G.vexnum; v++ )
{ final[v] = false; D[v] = G.arcs[v0][v];
}；
D[v0] = 0; final[v0] = true;
for( i = 2; i <= G.vexnum; i++ )
{ min = ∞ ;
for( w = 1; w < G.vexnum; w++ )
if( !final[w] ) //w在 V-S中
if( D[w] < min ) { v = w; min = D[w] }
final[v] = true;
for( w = 1; w < G.vexnum; w++ )
if( !final[w] && ( min + G.arcs[v][w] < D[w] ))
D[w] = min + G.arcs[v][w];
}
} //shortpath_DIJ 算法分析：时间复杂度 O(n2)
第七章 图第 110页问题：对于给定的有向图 G=(V,E)，要对 G中任意一对顶点有序对 v,w(v≠w)，找出 v到 w的最短路径。
方法一 依次把有向图 G的每个顶点作为源点，重复执行 Dijkstra算法 n次，即可求得每一对顶点之间的最短路径。其时间复杂度是 O(n3)。
方法二 采用一种更为直接的方式，计算每一对顶点之间最短路径，即由 Floyd提出的一种算法，其时间复杂度虽仍是 O(n3)，但形式上却较为简单。
Floyd算法中仍采用带权邻接矩阵以表示一个有向网。
每一对顶点之间的最短路径第七章 图第 111页分析：如何求 Vi到 Vj的最短路径？
对于 1≤i,j≤n,若 Vi到 Vj 有弧，则 Vi到 Vj 存在一条长度为
cost[i,j]的路径，但它不一定是最短路径，因为可能存在一条从 Vi
到 Vj但包含其它顶点为中间点的路径。应该依次考虑 Vi到 Vj 能否有以顶点 1,2,…,n 为中间点的更短路径 。
(1) 首先考虑从 Vi到 Vj 是否有以顶点 V1为中间点的路径，即
Vi— V1— Vj若有，则取 Vi— Vj与 Vi— V1— Vj中路径长度较短者，作为从 Vi到 Vj的中间顶点的 序号不大于 1的最短路径；
每一对顶点之间的最短路径必须先求出所有顶点对 (Vi,Vj)的中间顶点的 序号不大于 1的最短路径，才能进行 (2)。
(2) 其次考虑从 Vi到 Vj 是否有包含顶点 V2为中间点的路径，即
Vi-… -V2-…V j,如果 Vi-… -V2和 V2-… -Vj分别是当前找到的中间顶点的序号不大于 1的最短路径，那么 Vi-… -V2-…V j.就有可能是从 Vi到
Vj的中间顶点的序号不大于 2的最短路径。将它与已经得到的从 Vi
到 Vj的中间顶点序号不大于 1的最短路径相比较,从中选出中间顶点的序号不大于 2的最短路径；
第七章 图第 112页
(3) 依次类推。一般地，若 Vi-… -Vk 和 Vk -…V j.分别是 从 Vi到 Vk
和从 Vk到 Vj的中间顶点的序号不大于 k-1的最短路径,则将 Vi-… -Vk-
…V j和已得到的从 Vi到 Vj且中间顶点序号不大于 k-1的最短路程相比较，取其短,则是从 Vi到 Vj且中间顶点序号不大于 k的最短路程 ；
每一对顶点之间的最短路径
(4) 经过 n次比较后，最后求得的必是从 Vi到 Vj的最短路径；
实现上述算法的关键,要保留每一步求得的、所有顶点对之间的当前最短路径长度。为此，定义一个 n阶方阵序列 A(0),A(1)，
···,A(n),其中
A(0)[i,j]=cost[i.j]
A(k)[i,j] = Min{A(k-1)[i,j],A(k-1)[i,k]+A(k-1)[k,j]},1≤k≤n
这里,A(k)[i,j]表示从 Vi到 Vj的中间顶点的序号不大于 k的最短路径长度。故 Floyd算法的基本思想是：从 A(0)开始，递推地生成矩阵序列 A(1),A(2),··,A(n)。
第七章 图第 113页
Floyd 算法描述
void shortpath_FLOYD( Mgraph G,PathMatrix P[],
DistanceMatrix &D )
{//最短路径 P，带权长度为 D。如果 P[v][w][u]=true则 v,w是最短路径顶点
for( v =1; v <= G.vexnum; v++ )
for( w = 1; w <= G.vexnum; w++ ){
D[v][w] = G.arcs[v][w];
for( u = 1; u <= G.vexnum; u++ ) P[v][w][u] = false;
if( D[v][w] < ∞ )
{ P[v][w][v] = ture; P[v][w][w] = true; }
};
for( u = 1; u <= G.vexnum; u++ )
for( v = 1; v <= G.vexnum; v++ )
for( w = 1; w <= G.vexnum; w++ )
if( D[v][u]+ D[u][w] < D[v][w] )
{ D[v][w] = D[v][u] + D[u][w];
for( i = 0; i <= G.vexnum; i++ )
P[v][w][i] = P[v][u][i] || P[u][w][i];
};
} //shortpath_FLOYD
第七章 图第 114页示例 26 设带权有向图 D2及对应的邻接矩阵如下所示
1 2
3
6
4
b
2
11
a
3
c(a) (b)
0 4 11
6 0 2
3 ∞ 0
当 i=j时 D[i,j]=0，即对角线上元素为零
A
(0 )
A
( 1 )
A
(2 )
A
(3 )
A
1 2 3 1 2 3 1 2 3 1 2 3
1 0 4 11 0 4 11 0 4 6 0 4 6
2 6 0 2 6 0 2 6 0 2 5 0 2
3 3 0 3 7 0 3 7 0 3 7 0
P A T H
( 0 )
P A T H
( 1 )
P A T H
( 2 )
P A T H
( 3 )P A T H
1 2 3 1 2 3 1 2 3 1 2 3
1 AB AC AB AC AB A B C AB A B C
2 BA BC BA BC BA BC BCA BC
3 CA CA C A B CA C A B CA C A B
图 7.39图 7.38中有向图的各对顶点间的最短路径及其路径长度第七章 图第 115页示例 27 对下述有向图
100
60
10
30
1050
20
V1
V5
V4V3
V2
可写出 A(0),A(1)，
A(2),···,A(5)诸递推矩阵的内容
A(1) =A(0)
0 10 ∞ 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0
A(0)=
A(5) =A(4)
A(2)=
0 10 60 30 100
∞ 0 50 ∞ ∞
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 60
∞ ∞ ∞ ∞ 0
A(4)=
0 10 50 30 60
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0
0 10 60 30 70
∞ 0 50 ∞ 60
∞ ∞ 0 ∞ 10
∞ ∞ 20 0 30
∞ ∞ ∞ ∞ 0
A(3)=
第七章 图第 116页第七章 图 小结内容提要
● 图的定义和术语
● 图的存储结构 —— 数组表示法（邻接矩阵）、邻接表
、十字链表、邻接多重表
● 图的遍历 —— 深度优先搜索、广度优先搜索
● 构造连通图的最小生成树的 Prim 算法的
Kruskal 算法
● AOV-网及拓扑排序
● AOE-网及关键路径
● 有向网的最短路径问题
● 两类求最短路径的算法 —— Dijkstra 算法和
Floyd 算法第七章 图第 117页第七章 图 小结学习要点
● 熟悉图的有关术语和概念
● 熟悉图的各种存储结构，并能根据问题的要求选择合适的存储结构
● 掌握遍历图的两种算法
● 掌握求最小生成树、拓扑排序、关键路径以及最短路径的各种算法
● 了解图的基本应用
