第六章 图
§ 6.1 图的定义和术语
图 (Graph)—— 图 G是由两个集合 V(G)和 E(G)组成的,
记为 G=(V,E)
其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对或有序对
有向图 —— 有向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为 <v,w>,v,w是顶点,v为弧尾,w为弧头
无向图 —— 无向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对，记为（ v,w）
或（ w,v),并且（ v,w)=(w,v)
例
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}
E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
有向完备图 —— n个顶点的有向图最大边数是 n(n-1)
无向完备图 —— n个顶点的无向图最大边数是 n(n-1)/2
权 —— 与图的边或弧相关的数叫 ~
网 —— 带权的图叫 ~
子图 —— 如果图 G(V,E)和图 G‘(V’,E‘),满足：
V’?V
E’?E
则称 G‘为 G的子图
顶点的度
无向图中，顶点的度为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度：以该顶点为头的弧的数目
出度：以该顶点为尾的弧的数目
路径 —— 路径是顶点的序列 V={Vi0,Vi1,……V in},满足
(Vij-1,Vij)?E 或 <Vij-1,Vij>?E,(1<j?n)
路径长度 —— 沿路径边的数目或沿路径各边权值之和
回路 —— 第一个顶点和最后一个顶点相同的路径叫 ~
简单路径 —— 序列中顶点不重复出现的路径叫 ~
简单回路 —— 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫 ~
连通 —— 从顶点 V到顶点 W有一条路径，则说 V和 W是连通的
连通图 —— 图中任意两个顶点都是连通的叫 ~
连通分量 —— 非连通图的每一个连通部分叫 ~
强连通图 —— 有向图中，如果对每一对 Vi,Vj?V,Vi?Vj,
从 Vi到 Vj 和从 Vj到 Vi都存在路径，则称 G是 ~
例 2
1 3
2
1 3
有向完备图 无向完备图
3
5
6
例
2 4 5
1 3 6
图与子图 例
2 4 5
1 3 6
G1
顶点 2入度,1 出度,3
顶点 4入度,1 出度,0
例
1 5 7
3 2 4
G2
6
顶点 5的度,3
顶点 2的度,4
例
1 5 7
3 2 4
G2
6
例
2 4 5
1 3 6
G1
路径,1,2,3,5,6,3
路径长度,5
简单路径,1,2,3,5
回路,1,2,3,5,6,3,1
简单回路,3,5,6,3
路径,1,2,5,7,6,5,2,3
路径长度,7
简单路径,1,2,5,7,6
回路,1,2,5,7,6,5,2,1
简单回路,1,2,3,1
连通图例
2 4 5
1 3 6
强连通图3
5
6
例非连通图连通分量例
2 4 5
1 3 6
§ 6.2 图的存储结构
多重链表例
G1
2
4
1
3
例 1
5
3
2
4 G2
V1
V2 ^ ^V4 ^
V3 ^
^ V1 V2
V4 ^ V5 ^
V3
邻接矩阵 —— 表示顶点间相联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点的图,G的邻接矩阵 A是具有以下性质的 n阶方阵
，其它0
E ( G )v,v或)v,(v若1,],[ jijijiA
例
G1
2
4
1
3
例 1
5
3
2
4 G2
00110
00101
11010
10101
01010
0001
1000
0000
0110?
特点：
无向图的邻接矩阵对称，可压缩存储；有 n个顶点的无向图需存储空间为 n(n+1)/2
有向图邻接矩阵不一定对称；有 n个顶点的有向图需存储空间为 n2
无向图中顶点 Vi的度 TD(Vi)是邻接矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行元素之和
顶点 Vi的入度是 A中第 i列元素之和
网络的邻接矩阵可定义为：
，其它0
E ( G )v,v或)v,(v若,],[ jijiijjiA?
06183
60240
12007
84005
30750
例 1
4
5
2
3
7
5
3
1
8
6
4
2
关联矩阵 —— 表示顶点与边的关联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点,e?0条边的图,G的关联矩阵 A是具有以下性质的 n?e阶矩阵
为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：
iji
ji
iji
jiA
,1
,0
,1
],[
边不相连顶点与，
边相连顶点与，无向图：
ji
jijiA
0
1],[
1100
0110
0001
1011?
4321
例
G1
2
4
1
3
1
2
3
4
例 1
5
3
2
4 G2
1
2
3
4
5
6
110000
000110
011100
101001
000011
4321 5 6
例 B
D
A C
1
2
3
4
5
6
A
B
C
D
4321 5 6
101011
110000
011100
000111
特点
关联矩阵每列只有两个非零元素，是稀疏矩阵； n越大，零元素比率越大
无向图中顶点 Vi的度 TD(Vi)是关联矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行中,1”的个数
顶点 Vi的入度是 A中第 i行中,-1”的个数
邻接表
实现：为图中每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点 Vi的边（有向图中指以 Vi为尾的弧）
typedef struct node
{ int adjvex; //邻接点域，存放与 Vi邻接的点在表头数组中的位置
struct node *next; //链域，指示下一条边或弧
}JD;
adjvex next
表头接点：
typedef struct tnode
{ int vexdata; //存放顶点信息
struct node *firstarc; //指示第一个邻接点
}TD;
TD ga[M]; //ga[0]不用
vexdata firstarc
例
G1
b
d
a
c
例 a
e
c
b
d G2
1
2
3
4
a
c
d
b
vexdata firstarc
3 2
4
1
^
^
^
^
adjvex next
1
2
3
4
a
c
d
b
vexdata firstarc
4
2
1
2 ^
^
^
adjvex next
5 e
4
3 5 ^1
5
3
2 3 ^
特点
无向图中顶点 Vi的度为第 i个单链表中的结点数
有向图中
顶点 Vi的出度为第 i个单链表中的结点个数
顶点 Vi的入度为整个 单链表中邻接点域值是 i的结点个数
逆邻接表：有向图中对每个结点建立以 Vi为头的弧的单链表例
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
4
1 ^
1 ^
^
3 ^
adjvex next
有向图的十字链表表示法弧结点：
typedef struct arcnode
{ int tailvex,headvex; //弧尾、弧头在表头数组中位置
struct arcnode *hlink； //指向弧头相同的下一条弧
struct arcnode *tlink; //指向弧尾相同的下一条弧
}AD;
tailvex headvex hlink tlink
顶点结点：
typedef struct dnode
{ int data; //存与顶点有关信息
struct arcnode *firstin； //指向以该顶点为弧头的第一个弧结点
struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点
}DD;
DD g[M]; //g[0]不用
data firstin firstout
例 b
d
a
c
a
b
c
d
1
2
3
4
1 31 2
3 43 1
4 34 24 1
^
^
^
^^ ^ ^
^
无向图的邻接多重表表示法顶点结点：
typedef struct dnode
{ int data; //存与顶点有关的信息
struct node *firstedge; //指向第一条依附于该顶点的边
}DD;
DD ga[M]; //ga[0]不用 data firstedge
边结点：
typedef struct node
{ int mark; //标志域
int ivex,jvex; //该边依附的两个顶点在表头数组中位置
struct node *ilink,*jlink; //分别指向依附于 ivex和 jvex的下一条边
}JD;
mark ivex ilink jvex jlink
例 a
e
c
b
d
1
2
3
4
a
c
d
b
5 e
1 2 1 4
3 43 2
3 5 5 2
^
^
^
^^
§ 6.3 图的遍历
深度优先遍历 (DFS)
方法：从图的某一顶点 V0出发，访问此顶点；然后依次从 V0的未被访问的邻接点出发，深度优先遍历图，
直至图中所有和 V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
V1
V2
V4 V5
V3
V7V6
V8
例例 V1
V2
V4
V5 V3
V7
V6
V8
深度遍历,V1?V2?V4?V8?V5?V6?V3?V7
深度遍历,V1?V2?V4?V8?V5?V6?V3?V7
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?V2?V4?V8?V3?V6?V7?V5
深度优先遍历算法
递归算法开始访问 V0,置 标志求 V0邻接点有邻接点 w
求下一邻接点w?V0
W访问过结束
N
Y
N
Y
DFS
开始标志数组初始化
Vi=1
Vi访问过
DFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_1.c
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
V3?V7?V6?V2?V5?V8?V4
V1
V2
V4 V5
V3
V7V6
V8
例
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
^4
8 2 ^
6
7
8
6
7
8
7 ^
^
^
深度遍历,V1?V3?V7?V6?V2?V4?V8?V5
广度优先遍历 (BFS)
方法：从图的某一顶点 V0出发，访问此顶点后，依次访问 V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，
重复上述过程，直至图中所有顶点都被访问为止
V1
V2
V4 V5
V3
V7V6
V8
例广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
V1
V2
V4 V5
V3
V7V6
V8
例例 V1
V2
V4
V5 V3
V7
V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
V1
V2
V4 V5
V3
V7V6
V8
例广度遍历,V1?V2?V3?V4?V6?V7?V8?V5
广度优先遍历算法开始标志数组初始化
Vi=1
Vi访问过
BFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_2.c
开始访问 V0,置 标志求 V邻接点 w
w存在吗 V下一邻接点?w
w访问过结束
N
Y
N
Y
BFS
初始化队列
V0入队队列空吗队头 V出队 访问 w,置 标志
w入队
N
a
a
Y
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
1
f
r
遍历序列,1
0 1 2 3 4 5
4
f
r
遍历序列,1 4
0 1 2 3 4 5
4 3
f
r
遍历序列,1 4 3
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
4 3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
f
r
遍历序列,1 4 3 2 5
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
§ 6.4 生成树
生成树
定义：所有顶点均由边连接在一起，但不存在回路的图叫 ~
深度优先生成树与广度优先生成树
生成森林：非连通图每个连通分量的生成树一起组成非连通图的 ~
说明
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树
G
H
K I
V1
V2
V4 V5
V3
V7V6
V8
例 深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
V1
V2
V4
V5
V3
V7
V6
V8
深度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
广度优先生成树
V1
V2
V4 V5
V3
V7V6
V8V1
V2
V4 V5
V3
V7V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
例
A B
L M
C
F
D E
G H
KI
J
A
B
L
M
C F
J
D
E
G
H
K I
深度优先生成森林
最小生成树
问题提出要在 n个城市间建立通信联络网，
顶点 —— 表示城市权 —— 城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 ——— 最小代价生成树
问题分析
1
65
43
27
13
17
9
18
12
7 5
24
10
n个城市间，最多可设置 n(n-1)/2条线路
n个城市间建立通信网，只需 n-1条线路问题转化为：如何在可能的线路中选择 n-1条，能把所有城市（顶点）均连起来，且总耗费
（各边权值之和）最小
构造最小生成树方法
方法一：普里姆 (Prim)算法
算法思想：设 N=(V,{E})是连通网,TE是 N上最小生成树中边的集合
初始令 U={u0},(u0?V),TE=?
在所有 u?U,v?V-U的边 (u,v)?E中，找一条代价最小的边 (u0,v0)
将 (u0,v0)并入集合 TE,同时 v0并入 U
重复上述操作直至 U=V为止，则 T=(V,{TE})为 N的最小生成树
算法实现：图用邻接矩阵表示
算法描述
算法评价,T(n)=O(n2)
Ch6_3.c
例 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
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
方法二：克鲁斯卡尔 (Kruskal)算法
算法思想：设连通网 N=(V,{E}),令最小生成树
初始状态为只有 n个顶点而无边的非连通图 T=(V,{?})，每个顶点自成一个连通分量
在 E中选取代价最小的边，若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至 T中所有顶点都在同一连通分量上为止例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
（ 0）用顶点数组和边数组存放顶点和边信息
（ 1）初始时，令每个顶点的 jihe互不相同；每个边的 flag为 0
（ 2）选出权值最小且 flag为 0的边
（ 3）若该边依附的两个顶点的 jihe 值不同，即非连通，则令该边的 flag=1,选中该边；再令该边依附的两顶点的 jihe
以及两集合中所有顶点的 jihe 相同若该边依附的两个顶点的 jihe 值相同，即连通，则令该边的 flag=2,即舍去该边
（ 4）重复上述步骤，直到选出 n-1条边为止顶点结点：
typedef struct
{ int data; //顶点信息
int jihe;
}VEX;
边结点：
typedef struct
{ int vexh,vext; //边依附的两顶点
int weight; //边的权值
int flag; //标志域
}EDGE;
算法实现：
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
Ch6_30.c
算法描述：
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
§ 6.5 拓扑排序
问题提出：学生选修课程问题顶点 —— 表示课程有向弧 —— 表示先决条件，若课程 i是课程 j的先决条件，
则图中有弧 <i,j>
学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业 —— 拓扑排序
定义
AOV网 —— 用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网 (Activity On Vertex
network),简称 AOV网
若 <vi,vj>是图中有向边，则 vi是 vj的直接前驱； vj是 vi的直接后继
AOV网中不允许有回路，这意味着某项活动以自己为先决条件
拓扑排序 —— 把 AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 ~
检测 AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该
AOV网必定不存在环
拓扑排序的方法
在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止例课程代号 课程名称 先修棵
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
无
C1
C1,C2
C1
C3,C4
C11
C3.C5
C3,C6
无
C9
C9
C1,C9,C10
程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
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网的拓扑序列不是唯一的
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
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）
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）
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）
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）
算法实现
以邻接表作存储结构
把邻接表中所有入度为 0的顶点进栈
栈非空时，输出栈顶元素 Vj并退栈；在邻接表中查找
Vj的直接后继 Vk,把 Vk的入度减 1；若 Vk的入度为 0则进栈
重复上述操作直至栈空为止。若栈空时输出的顶点个数不是 n,则有向图有环；否则，拓扑排序完毕邻接表结点：
typedef struct node
{ int vex; //顶点域
struct node *next; //链域
}JD;
表头结点：
typedef struct tnode
{ int in; //入度域
struct node *link; //链域
}TD;
TD g[M]; //g[0]不用
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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=NULL
算法分析建邻接表,T(n)=O(e)
搜索入度为 0的顶点的时间,T(n)=O(n)
拓扑排序,T(n)=O(n+e)
Ch6_4.c
§ 6.6 关键路径
问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；
每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有 11项活动,9个事件事件 V1—— 表示整个工程开始事件 V9—— 表示整个工程结束问题：（ 1）完成整项工程至少需要多少时间？
（ 2）哪些活动是影响工程进度的关键？
9
8
7
64
5
3
2
1
a6=2
定义
AOE网 (Activity On Edge)—— 也叫边表示活动的网。
AOE网是一个带权的有向无环图，其中顶点表示事件，
弧表示活动，权表示活动持续时间
路径长度 —— 路径上各活动持续时间之和
关键路径 —— 路径长度最长的路径叫 ~
Ve(j)—— 表示事件 Vj的最早发生时间
Vl(j)—— 表示事件 Vj的最迟发生时间
e(i)—— 表示活动 ai的最早开始时间
l(i)—— 表示活动 ai的最迟开始时间
l(i)-e(i)—— 表示完成活动 ai的时间余量
关键活动 —— 关键路径上的活动叫 ~，即 l(i)=e(i)的活动
问题分析
如何找 e(i)=l(i)的关键活动？
设活动 ai用弧 <j,k>表示，其持续时间记为,dut(<j,k>)
则有：（ 1） e(i)=Ve(j)
（ 2） l(i)=Vl(k)-dut(<j,k>) j k
ai
如何求 Ve(j)和 Vl(j)？
(1)从 Ve(1)=0开始向前递推为头的弧的集合是所有以其中 jT
njTjijidutiVeM a xjVe
i
2,,) },,()({)(
(2)从 Vl(n)=Ve(n)开始向后递推为尾的弧的集合是所有以其中 iS
niSjijid u tjVlM i niVl
j
11,,) },,()({)(
求关键路径步骤
求 Ve(i)
求 Vl(j)
求 e(i)
求 l(i)
计算 l(i)-e(i)
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
算法实现
以邻接表作存储结构
从源点 V1出发，令 Ve[1]=0,按拓扑序列求各顶点的 Ve[i]
从汇点 Vn出发，令 Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的 Vl[i]
根据各顶点的 Ve和 Vl值，计算每条弧的 e[i]和 l[i],找出
e[i]=l[i]的关键活动邻接表结点：
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]不用
算法描述
输入顶点和弧信息，建立其邻接表
计算每个顶点的入度
对其进行拓扑排序
排序过程中求顶点的 Ve[i]
将得到的拓扑序列进栈
按逆拓扑序列求顶点的 Vl[i]
计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动
Ch6_20.c
9
8
7
64
5
3
2
1
a6=2
9
8
7
64
5
3
2
1
a6=2
in link vex nextvexdata length
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
0
1
1
1
2
1
1
2
2
2 6 3 4 4 5 ^
7 9
^5 1
^6 2
^5 1
^8 7
^8 4
^9 10
^9 4
^
§ 6.7 最短路径
问题提出用带权的有向图表示一个交通运输网，图中：
顶点 —— 表示城市边 —— 表示城市间的交通联系权 —— 表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 —— 最短路径
从某个源点到其余各顶点的最短路径
5
1
6
4
3
2
0
8
5
6 2
30
13
7
17
32
9
13
长度最短路径
<V0,V1>
<V0,V2>
<V0,V2,V3>
<V0,V2,V3,V4>
<V0,V2,V3,V4,V5>
<V0,V1,V6>
8
13
19
21
20
迪杰斯特拉 (Dijkstra)算法思想按路径长度递增次序产生最短路径算法：
把 V分成两组：
（ 1） S,已求出最短路径的顶点的集合
（ 2） V-S=T,尚未确定最短路径的顶点集合将 T中顶点按最短路径递增的次序加入到 S中，
保证：（ 1）从源点 V0到 S中各顶点的最短路径长度都不大于从 V0到 T中任何顶点的最短路径长度
（ 2）每个顶点对应一个距离值
S中顶点：从 V0到此顶点的最短路径长度
T中顶点：从 V0到此顶点的只包括 S中顶点作中间顶点的最短路径长度依据：可以证明 V0到 T中顶点 Vk的最短路径，或是从 V0到 Vk的直接路径的权值；或是从 V0经 S中顶点到 Vk的路径权值之和
（反证法可证）
求最短路径步骤
初使时令 S={V0},T={其余顶点 },T中顶点对应的距离值
若存在 <V0,Vi>，为 <V0,Vi>弧上的权值
若不存在 <V0,Vi>,为?
从 T中选取一个其距离值为最小的顶点 W，加入 S
对 T中顶点的距离值进行修改：若加进 W作中间顶点，从 V0
到 Vi的距离值比不加 W的路径要短，则修改此距离值
重复上述步骤，直到 S中包含所有顶点，即 S=V为止
13
<V0,V1>
8
<V0,V2>
30
<V0,V4>
32
<V0,V6>
V2:8
<V0,V2>
13
<V0,V1>
-------
13
<V0,V2,V3>
30
<V0,V4>
32
<V0,V6>
V1:13
<V0,V1>
-------
-------
13
<V0,V2,V3>
30
<V0,V4>
22
<V0,V1,V5>
20
<V0,V1,V6>
V3:13
<V0,V2,V3>
-------
-------
-------
19
<V0,V2,V3,V4>
22
<V0,V1,V5>
20
<V0,V1,V6>
V4:19
<V0,V2,V3,V4>
终点 从 V0到各终点的最短路径及其长度
V1
V2
V3
V4
V5
V6
Vj
--------
--------
--------
--------
21
<V0,V2,V3,V4,V5>
20
<V0,V1,V6>
V6:20
<V0,V1,V6>
5
1
6
4
3
2
0
8
5
6 2
3
0
13
7
17
32
9
算法实现
图用带权邻接矩阵存储 ad[][]
数组 dist[]存放当前找到的从源点 V0到每个终点的最短路径长度，其初态为图中直接路径权值
数组 pre[]表示从 V0到各终点的最短路径上，此顶点的前一顶点的序号；若从 V0到某终点无路径，则用 0作为其前一顶点的序号
算法描述
6
2
7
5
4
3
1
8
5
6 2
30
13
7
17
32
9
0
170
20
60
50
790
32308131
[ ] [ ]ad
dist
0 1 2 3 4 5 6
0 13 8? 30? 32
pre
0 1 2 3 4 5 6
0 1 1 0 1 0 1
(1)k=1
Ch6_5.c
1
13
3
1
22 20
2 2
19
4
1
21
5
1
1
1
长度最短路径
13<V1,V2>
8<V1,V3>
13<V1,V3,V4>
19<V1,V3,V4,V5>
21<V1,V3,V4,V5,V6>
20<V1,V2,V7>
算法分析,T(n)=O(n2)
每一对顶点之间的最短路径
方法一：每次以一个顶点为源点，重复执行 Dijkstra算法 n次 —— T(n)=O(n3)
方法二：弗洛伊德 (Floyd)算法
算法思想：逐个顶点试探法
求最短路径步骤
初始时设置一个 n阶方阵，令其对角线元素为 0，若存在弧 <Vi,Vj>,则对应元素为权值；否则为?
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
所有顶点试探完毕，算法结束例
A
C
B
2
6
4
3 11
0 4 11
6 0 2
3? 0
初始,路径,AB ACBA BC
CA
0 4 6
6 0 2
3 7 0
加入 V2,路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
算法实现
图用邻接矩阵存储
length[][]存放最短路径长度
path[i][j]是从 Vi到 Vj的最短路径上 Vj前一顶点序号
算法描述例
1
3
2
2
6
4
3 11
初始：
0 4 11
6 0 2
3? 0
length=
0 1 1
2 0 2
3 0 0
path=
加入 V1,0 4 11
6 0 2
3 7 0
length=
0 1 1
2 0 2
3 1 0
path=
加入 V2,0 4 6
6 0 2
3 7 0
length=
0 1 2
2 0 2
3 1 0
path=
加入 V3,0 4 6
5 0 2
3 7 0
length=
0 1 2
3 0 2
3 1 0
path=
Ch6_6.c
算法分析,T(n)=O(n3)
§ 6.1 图的定义和术语
图 (Graph)—— 图 G是由两个集合 V(G)和 E(G)组成的,
记为 G=(V,E)
其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对或有序对
有向图 —— 有向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为 <v,w>,v,w是顶点,v为弧尾,w为弧头
无向图 —— 无向图 G是由两个集合 V(G)和 E(G)组成的其中,V(G)是顶点的非空有限集
E(G)是边的有限集合，边是顶点的无序对，记为（ v,w）
或（ w,v),并且（ v,w)=(w,v)
例
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}
E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
有向完备图 —— n个顶点的有向图最大边数是 n(n-1)
无向完备图 —— n个顶点的无向图最大边数是 n(n-1)/2
权 —— 与图的边或弧相关的数叫 ~
网 —— 带权的图叫 ~
子图 —— 如果图 G(V,E)和图 G‘(V’,E‘),满足：
V’?V
E’?E
则称 G‘为 G的子图
顶点的度
无向图中，顶点的度为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度：以该顶点为头的弧的数目
出度：以该顶点为尾的弧的数目
路径 —— 路径是顶点的序列 V={Vi0,Vi1,……V in},满足
(Vij-1,Vij)?E 或 <Vij-1,Vij>?E,(1<j?n)
路径长度 —— 沿路径边的数目或沿路径各边权值之和
回路 —— 第一个顶点和最后一个顶点相同的路径叫 ~
简单路径 —— 序列中顶点不重复出现的路径叫 ~
简单回路 —— 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫 ~
连通 —— 从顶点 V到顶点 W有一条路径，则说 V和 W是连通的
连通图 —— 图中任意两个顶点都是连通的叫 ~
连通分量 —— 非连通图的每一个连通部分叫 ~
强连通图 —— 有向图中，如果对每一对 Vi,Vj?V,Vi?Vj,
从 Vi到 Vj 和从 Vj到 Vi都存在路径，则称 G是 ~
例 2
1 3
2
1 3
有向完备图 无向完备图
3
5
6
例
2 4 5
1 3 6
图与子图 例
2 4 5
1 3 6
G1
顶点 2入度,1 出度,3
顶点 4入度,1 出度,0
例
1 5 7
3 2 4
G2
6
顶点 5的度,3
顶点 2的度,4
例
1 5 7
3 2 4
G2
6
例
2 4 5
1 3 6
G1
路径,1,2,3,5,6,3
路径长度,5
简单路径,1,2,3,5
回路,1,2,3,5,6,3,1
简单回路,3,5,6,3
路径,1,2,5,7,6,5,2,3
路径长度,7
简单路径,1,2,5,7,6
回路,1,2,5,7,6,5,2,1
简单回路,1,2,3,1
连通图例
2 4 5
1 3 6
强连通图3
5
6
例非连通图连通分量例
2 4 5
1 3 6
§ 6.2 图的存储结构
多重链表例
G1
2
4
1
3
例 1
5
3
2
4 G2
V1
V2 ^ ^V4 ^
V3 ^
^ V1 V2
V4 ^ V5 ^
V3
邻接矩阵 —— 表示顶点间相联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点的图,G的邻接矩阵 A是具有以下性质的 n阶方阵
，其它0
E ( G )v,v或)v,(v若1,],[ jijijiA
例
G1
2
4
1
3
例 1
5
3
2
4 G2
00110
00101
11010
10101
01010
0001
1000
0000
0110?
特点：
无向图的邻接矩阵对称，可压缩存储；有 n个顶点的无向图需存储空间为 n(n+1)/2
有向图邻接矩阵不一定对称；有 n个顶点的有向图需存储空间为 n2
无向图中顶点 Vi的度 TD(Vi)是邻接矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行元素之和
顶点 Vi的入度是 A中第 i列元素之和
网络的邻接矩阵可定义为：
，其它0
E ( G )v,v或)v,(v若,],[ jijiijjiA?
06183
60240
12007
84005
30750
例 1
4
5
2
3
7
5
3
1
8
6
4
2
关联矩阵 —— 表示顶点与边的关联关系的矩阵
定义,设 G=(V,E)是有 n?1个顶点,e?0条边的图,G的关联矩阵 A是具有以下性质的 n?e阶矩阵
为头边相连，且顶点与边不相连顶点与为尾边相连，且顶点与有向图：
iji
ji
iji
jiA
,1
,0
,1
],[
边不相连顶点与，
边相连顶点与，无向图：
ji
jijiA
0
1],[
1100
0110
0001
1011?
4321
例
G1
2
4
1
3
1
2
3
4
例 1
5
3
2
4 G2
1
2
3
4
5
6
110000
000110
011100
101001
000011
4321 5 6
例 B
D
A C
1
2
3
4
5
6
A
B
C
D
4321 5 6
101011
110000
011100
000111
特点
关联矩阵每列只有两个非零元素，是稀疏矩阵； n越大，零元素比率越大
无向图中顶点 Vi的度 TD(Vi)是关联矩阵 A中第 i行元素之和
有向图中，
顶点 Vi的出度是 A中第 i行中,1”的个数
顶点 Vi的入度是 A中第 i行中,-1”的个数
邻接表
实现：为图中每个顶点建立一个单链表，第 i个单链表中的结点表示依附于顶点 Vi的边（有向图中指以 Vi为尾的弧）
typedef struct node
{ int adjvex; //邻接点域，存放与 Vi邻接的点在表头数组中的位置
struct node *next; //链域，指示下一条边或弧
}JD;
adjvex next
表头接点：
typedef struct tnode
{ int vexdata; //存放顶点信息
struct node *firstarc; //指示第一个邻接点
}TD;
TD ga[M]; //ga[0]不用
vexdata firstarc
例
G1
b
d
a
c
例 a
e
c
b
d G2
1
2
3
4
a
c
d
b
vexdata firstarc
3 2
4
1
^
^
^
^
adjvex next
1
2
3
4
a
c
d
b
vexdata firstarc
4
2
1
2 ^
^
^
adjvex next
5 e
4
3 5 ^1
5
3
2 3 ^
特点
无向图中顶点 Vi的度为第 i个单链表中的结点数
有向图中
顶点 Vi的出度为第 i个单链表中的结点个数
顶点 Vi的入度为整个 单链表中邻接点域值是 i的结点个数
逆邻接表：有向图中对每个结点建立以 Vi为头的弧的单链表例
G1
b
d
a
c
1
2
3
4
a
c
d
b
vexdata firstarc
4
1 ^
1 ^
^
3 ^
adjvex next
有向图的十字链表表示法弧结点：
typedef struct arcnode
{ int tailvex,headvex; //弧尾、弧头在表头数组中位置
struct arcnode *hlink； //指向弧头相同的下一条弧
struct arcnode *tlink; //指向弧尾相同的下一条弧
}AD;
tailvex headvex hlink tlink
顶点结点：
typedef struct dnode
{ int data; //存与顶点有关信息
struct arcnode *firstin； //指向以该顶点为弧头的第一个弧结点
struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点
}DD;
DD g[M]; //g[0]不用
data firstin firstout
例 b
d
a
c
a
b
c
d
1
2
3
4
1 31 2
3 43 1
4 34 24 1
^
^
^
^^ ^ ^
^
无向图的邻接多重表表示法顶点结点：
typedef struct dnode
{ int data; //存与顶点有关的信息
struct node *firstedge; //指向第一条依附于该顶点的边
}DD;
DD ga[M]; //ga[0]不用 data firstedge
边结点：
typedef struct node
{ int mark; //标志域
int ivex,jvex; //该边依附的两个顶点在表头数组中位置
struct node *ilink,*jlink; //分别指向依附于 ivex和 jvex的下一条边
}JD;
mark ivex ilink jvex jlink
例 a
e
c
b
d
1
2
3
4
a
c
d
b
5 e
1 2 1 4
3 43 2
3 5 5 2
^
^
^
^^
§ 6.3 图的遍历
深度优先遍历 (DFS)
方法：从图的某一顶点 V0出发，访问此顶点；然后依次从 V0的未被访问的邻接点出发，深度优先遍历图，
直至图中所有和 V0相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
V1
V2
V4 V5
V3
V7V6
V8
例例 V1
V2
V4
V5 V3
V7
V6
V8
深度遍历,V1?V2?V4?V8?V5?V6?V3?V7
深度遍历,V1?V2?V4?V8?V5?V6?V3?V7
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?V2?V4?V8?V3?V6?V7?V5
深度优先遍历算法
递归算法开始访问 V0,置 标志求 V0邻接点有邻接点 w
求下一邻接点w?V0
W访问过结束
N
Y
N
Y
DFS
开始标志数组初始化
Vi=1
Vi访问过
DFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_1.c
V1
V2
V4 V5
V3
V7V6
V8
例深度遍历,V1?
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
4 1 ^5
1
2
8 2 ^
6
7
8
6
7
8
7 3
6 3
5 4
^
^
^
V3?V7?V6?V2?V5?V8?V4
V1
V2
V4 V5
V3
V7V6
V8
例
1
2
3
4
1
3
4
2
vexdata firstarc
2
7
8
3 ^
^
^
adjvex next
5 5
6
^4
8 2 ^
6
7
8
6
7
8
7 ^
^
^
深度遍历,V1?V3?V7?V6?V2?V4?V8?V5
广度优先遍历 (BFS)
方法：从图的某一顶点 V0出发，访问此顶点后，依次访问 V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，
重复上述过程，直至图中所有顶点都被访问为止
V1
V2
V4 V5
V3
V7V6
V8
例广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
V1
V2
V4 V5
V3
V7V6
V8
例例 V1
V2
V4
V5 V3
V7
V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
V1
V2
V4 V5
V3
V7V6
V8
例广度遍历,V1?V2?V3?V4?V6?V7?V8?V5
广度优先遍历算法开始标志数组初始化
Vi=1
Vi访问过
BFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Ch6_2.c
开始访问 V0,置 标志求 V邻接点 w
w存在吗 V下一邻接点?w
w访问过结束
N
Y
N
Y
BFS
初始化队列
V0入队队列空吗队头 V出队 访问 w,置 标志
w入队
N
a
a
Y
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
1
f
r
遍历序列,1
0 1 2 3 4 5
4
f
r
遍历序列,1 4
0 1 2 3 4 5
4 3
f
r
遍历序列,1 4 3
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
0 1 2 3 4 5
4 3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2
f
r
遍历序列,1 4 3 2
0 1 2 3 4 5
3 2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
2 5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
5
f
r
遍历序列,1 4 3 2 5
0 1 2 3 4 5
f
r
遍历序列,1 4 3 2 5
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdata firstarc
5
5
4 3 ^
^
^
adjvex next
5 5
1 ^5
1
1
4 3 ^
2
2
§ 6.4 生成树
生成树
定义：所有顶点均由边连接在一起，但不存在回路的图叫 ~
深度优先生成树与广度优先生成树
生成森林：非连通图每个连通分量的生成树一起组成非连通图的 ~
说明
一个图可以有许多棵不同的生成树
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树
G
H
K I
V1
V2
V4 V5
V3
V7V6
V8
例 深度遍历,V1?V2?V4?V8?V5?V3?V6?V7
V1
V2
V4
V5
V3
V7
V6
V8
深度优先生成树
V1
V2
V4 V5
V3
V7V6
V8
广度优先生成树
V1
V2
V4 V5
V3
V7V6
V8V1
V2
V4 V5
V3
V7V6
V8
广度遍历,V1?V2?V3?V4?V5?V6?V7?V8
例
A B
L M
C
F
D E
G H
KI
J
A
B
L
M
C F
J
D
E
G
H
K I
深度优先生成森林
最小生成树
问题提出要在 n个城市间建立通信联络网，
顶点 —— 表示城市权 —— 城市间建立通信线路所需花费代价希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 ——— 最小代价生成树
问题分析
1
65
43
27
13
17
9
18
12
7 5
24
10
n个城市间，最多可设置 n(n-1)/2条线路
n个城市间建立通信网，只需 n-1条线路问题转化为：如何在可能的线路中选择 n-1条，能把所有城市（顶点）均连起来，且总耗费
（各边权值之和）最小
构造最小生成树方法
方法一：普里姆 (Prim)算法
算法思想：设 N=(V,{E})是连通网,TE是 N上最小生成树中边的集合
初始令 U={u0},(u0?V),TE=?
在所有 u?U,v?V-U的边 (u,v)?E中，找一条代价最小的边 (u0,v0)
将 (u0,v0)并入集合 TE,同时 v0并入 U
重复上述操作直至 U=V为止，则 T=(V,{TE})为 N的最小生成树
算法实现：图用邻接矩阵表示
算法描述
算法评价,T(n)=O(n2)
Ch6_3.c
例 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
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
方法二：克鲁斯卡尔 (Kruskal)算法
算法思想：设连通网 N=(V,{E}),令最小生成树
初始状态为只有 n个顶点而无边的非连通图 T=(V,{?})，每个顶点自成一个连通分量
在 E中选取代价最小的边，若该边依附的顶点落在 T中不同的连通分量上，则将此边加入到 T中；否则，舍去此边，选取下一条代价最小的边
依此类推，直至 T中所有顶点都在同一连通分量上为止例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
1
65
4
3
2 1
23 4
5
（ 0）用顶点数组和边数组存放顶点和边信息
（ 1）初始时，令每个顶点的 jihe互不相同；每个边的 flag为 0
（ 2）选出权值最小且 flag为 0的边
（ 3）若该边依附的两个顶点的 jihe 值不同，即非连通，则令该边的 flag=1,选中该边；再令该边依附的两顶点的 jihe
以及两集合中所有顶点的 jihe 相同若该边依附的两个顶点的 jihe 值相同，即连通，则令该边的 flag=2,即舍去该边
（ 4）重复上述步骤，直到选出 n-1条边为止顶点结点：
typedef struct
{ int data; //顶点信息
int jihe;
}VEX;
边结点：
typedef struct
{ int vexh,vext; //边依附的两顶点
int weight; //边的权值
int flag; //标志域
}EDGE;
算法实现：
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
Ch6_30.c
算法描述：
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
§ 6.5 拓扑排序
问题提出：学生选修课程问题顶点 —— 表示课程有向弧 —— 表示先决条件，若课程 i是课程 j的先决条件，
则图中有弧 <i,j>
学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业 —— 拓扑排序
定义
AOV网 —— 用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网 (Activity On Vertex
network),简称 AOV网
若 <vi,vj>是图中有向边，则 vi是 vj的直接前驱； vj是 vi的直接后继
AOV网中不允许有回路，这意味着某项活动以自己为先决条件
拓扑排序 —— 把 AOV网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程叫 ~
检测 AOV网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该
AOV网必定不存在环
拓扑排序的方法
在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止例课程代号 课程名称 先修棵
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
无
C1
C1,C2
C1
C3,C4
C11
C3.C5
C3,C6
无
C9
C9
C1,C9,C10
程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
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网的拓扑序列不是唯一的
C1
C2
C3
C4 C5
C6
C7
C8
C9 C10
C11
C12
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）
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）
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）
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）
算法实现
以邻接表作存储结构
把邻接表中所有入度为 0的顶点进栈
栈非空时，输出栈顶元素 Vj并退栈；在邻接表中查找
Vj的直接后继 Vk,把 Vk的入度减 1；若 Vk的入度为 0则进栈
重复上述操作直至栈空为止。若栈空时输出的顶点个数不是 n,则有向图有环；否则，拓扑排序完毕邻接表结点：
typedef struct node
{ int vex; //顶点域
struct node *next; //链域
}JD;
表头结点：
typedef struct tnode
{ int in; //入度域
struct node *link; //链域
}TD;
TD g[M]; //g[0]不用
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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=NULL
算法分析建邻接表,T(n)=O(e)
搜索入度为 0的顶点的时间,T(n)=O(n)
拓扑排序,T(n)=O(n+e)
Ch6_4.c
§ 6.6 关键路径
问题提出把工程计划表示为有向图，用顶点表示事件，弧表示活动；
每个事件表示在它之前的活动已完成，在它之后的活动可以开始例 设一个工程有 11项活动,9个事件事件 V1—— 表示整个工程开始事件 V9—— 表示整个工程结束问题：（ 1）完成整项工程至少需要多少时间？
（ 2）哪些活动是影响工程进度的关键？
9
8
7
64
5
3
2
1
a6=2
定义
AOE网 (Activity On Edge)—— 也叫边表示活动的网。
AOE网是一个带权的有向无环图，其中顶点表示事件，
弧表示活动，权表示活动持续时间
路径长度 —— 路径上各活动持续时间之和
关键路径 —— 路径长度最长的路径叫 ~
Ve(j)—— 表示事件 Vj的最早发生时间
Vl(j)—— 表示事件 Vj的最迟发生时间
e(i)—— 表示活动 ai的最早开始时间
l(i)—— 表示活动 ai的最迟开始时间
l(i)-e(i)—— 表示完成活动 ai的时间余量
关键活动 —— 关键路径上的活动叫 ~，即 l(i)=e(i)的活动
问题分析
如何找 e(i)=l(i)的关键活动？
设活动 ai用弧 <j,k>表示，其持续时间记为,dut(<j,k>)
则有：（ 1） e(i)=Ve(j)
（ 2） l(i)=Vl(k)-dut(<j,k>) j k
ai
如何求 Ve(j)和 Vl(j)？
(1)从 Ve(1)=0开始向前递推为头的弧的集合是所有以其中 jT
njTjijidutiVeM a xjVe
i
2,,) },,()({)(
(2)从 Vl(n)=Ve(n)开始向后递推为尾的弧的集合是所有以其中 iS
niSjijid u tjVlM i niVl
j
11,,) },,()({)(
求关键路径步骤
求 Ve(i)
求 Vl(j)
求 e(i)
求 l(i)
计算 l(i)-e(i)
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
算法实现
以邻接表作存储结构
从源点 V1出发，令 Ve[1]=0,按拓扑序列求各顶点的 Ve[i]
从汇点 Vn出发，令 Vl[n]=Ve[n],按逆拓扑序列求其余各顶点的 Vl[i]
根据各顶点的 Ve和 Vl值，计算每条弧的 e[i]和 l[i],找出
e[i]=l[i]的关键活动邻接表结点：
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]不用
算法描述
输入顶点和弧信息，建立其邻接表
计算每个顶点的入度
对其进行拓扑排序
排序过程中求顶点的 Ve[i]
将得到的拓扑序列进栈
按逆拓扑序列求顶点的 Vl[i]
计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动
Ch6_20.c
9
8
7
64
5
3
2
1
a6=2
9
8
7
64
5
3
2
1
a6=2
in link vex nextvexdata length
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
0
1
1
1
2
1
1
2
2
2 6 3 4 4 5 ^
7 9
^5 1
^6 2
^5 1
^8 7
^8 4
^9 10
^9 4
^
§ 6.7 最短路径
问题提出用带权的有向图表示一个交通运输网，图中：
顶点 —— 表示城市边 —— 表示城市间的交通联系权 —— 表示此线路的长度或沿此线路运输所花的时间或费用等问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 —— 最短路径
从某个源点到其余各顶点的最短路径
5
1
6
4
3
2
0
8
5
6 2
30
13
7
17
32
9
13
长度最短路径
<V0,V1>
<V0,V2>
<V0,V2,V3>
<V0,V2,V3,V4>
<V0,V2,V3,V4,V5>
<V0,V1,V6>
8
13
19
21
20
迪杰斯特拉 (Dijkstra)算法思想按路径长度递增次序产生最短路径算法：
把 V分成两组：
（ 1） S,已求出最短路径的顶点的集合
（ 2） V-S=T,尚未确定最短路径的顶点集合将 T中顶点按最短路径递增的次序加入到 S中，
保证：（ 1）从源点 V0到 S中各顶点的最短路径长度都不大于从 V0到 T中任何顶点的最短路径长度
（ 2）每个顶点对应一个距离值
S中顶点：从 V0到此顶点的最短路径长度
T中顶点：从 V0到此顶点的只包括 S中顶点作中间顶点的最短路径长度依据：可以证明 V0到 T中顶点 Vk的最短路径，或是从 V0到 Vk的直接路径的权值；或是从 V0经 S中顶点到 Vk的路径权值之和
（反证法可证）
求最短路径步骤
初使时令 S={V0},T={其余顶点 },T中顶点对应的距离值
若存在 <V0,Vi>，为 <V0,Vi>弧上的权值
若不存在 <V0,Vi>,为?
从 T中选取一个其距离值为最小的顶点 W，加入 S
对 T中顶点的距离值进行修改：若加进 W作中间顶点，从 V0
到 Vi的距离值比不加 W的路径要短，则修改此距离值
重复上述步骤，直到 S中包含所有顶点，即 S=V为止
13
<V0,V1>
8
<V0,V2>
30
<V0,V4>
32
<V0,V6>
V2:8
<V0,V2>
13
<V0,V1>
-------
13
<V0,V2,V3>
30
<V0,V4>
32
<V0,V6>
V1:13
<V0,V1>
-------
-------
13
<V0,V2,V3>
30
<V0,V4>
22
<V0,V1,V5>
20
<V0,V1,V6>
V3:13
<V0,V2,V3>
-------
-------
-------
19
<V0,V2,V3,V4>
22
<V0,V1,V5>
20
<V0,V1,V6>
V4:19
<V0,V2,V3,V4>
终点 从 V0到各终点的最短路径及其长度
V1
V2
V3
V4
V5
V6
Vj
--------
--------
--------
--------
21
<V0,V2,V3,V4,V5>
20
<V0,V1,V6>
V6:20
<V0,V1,V6>
5
1
6
4
3
2
0
8
5
6 2
3
0
13
7
17
32
9
算法实现
图用带权邻接矩阵存储 ad[][]
数组 dist[]存放当前找到的从源点 V0到每个终点的最短路径长度，其初态为图中直接路径权值
数组 pre[]表示从 V0到各终点的最短路径上，此顶点的前一顶点的序号；若从 V0到某终点无路径，则用 0作为其前一顶点的序号
算法描述
6
2
7
5
4
3
1
8
5
6 2
30
13
7
17
32
9
0
170
20
60
50
790
32308131
[ ] [ ]ad
dist
0 1 2 3 4 5 6
0 13 8? 30? 32
pre
0 1 2 3 4 5 6
0 1 1 0 1 0 1
(1)k=1
Ch6_5.c
1
13
3
1
22 20
2 2
19
4
1
21
5
1
1
1
长度最短路径
13<V1,V2>
8<V1,V3>
13<V1,V3,V4>
19<V1,V3,V4,V5>
21<V1,V3,V4,V5,V6>
20<V1,V2,V7>
算法分析,T(n)=O(n2)
每一对顶点之间的最短路径
方法一：每次以一个顶点为源点，重复执行 Dijkstra算法 n次 —— T(n)=O(n3)
方法二：弗洛伊德 (Floyd)算法
算法思想：逐个顶点试探法
求最短路径步骤
初始时设置一个 n阶方阵，令其对角线元素为 0，若存在弧 <Vi,Vj>,则对应元素为权值；否则为?
逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值
所有顶点试探完毕，算法结束例
A
C
B
2
6
4
3 11
0 4 11
6 0 2
3? 0
初始,路径,AB ACBA BC
CA
0 4 6
6 0 2
3 7 0
加入 V2,路径：
AB ABC
BA BC
CA CAB
0 4 11
6 0 2
3 7 0
加入 V1,路径：
AB AC
BA BC
CA CAB
0 4 6
5 0 2
3 7 0
加入 V3,路径：
AB ABC
BCA BC
CA CAB
算法实现
图用邻接矩阵存储
length[][]存放最短路径长度
path[i][j]是从 Vi到 Vj的最短路径上 Vj前一顶点序号
算法描述例
1
3
2
2
6
4
3 11
初始：
0 4 11
6 0 2
3? 0
length=
0 1 1
2 0 2
3 0 0
path=
加入 V1,0 4 11
6 0 2
3 7 0
length=
0 1 1
2 0 2
3 1 0
path=
加入 V2,0 4 6
6 0 2
3 7 0
length=
0 1 2
2 0 2
3 1 0
path=
加入 V3,0 4 6
5 0 2
3 7 0
length=
0 1 2
3 0 2
3 1 0
path=
Ch6_6.c
算法分析,T(n)=O(n3)
