Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 1页第 7章 图和广义表
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 2页
7.1 图的定义和基本术语
图 (Graph)G是由两个集合 V和 E组成的偶对,表示为
G=（ V,E）
其中 V是有限非空的顶点集合,E是由顶点偶对表示的关系集合。
为了讨论方便，有时也将顶点集合为空的图称为空图。
一个图可以形式化定义为：
G=（ V,E）
V={v|v?data object}
E={<v,w>| v,w?V∧P(v,w)}
其中 v是数据元素，称为 顶点 （ vertex）,P(v,w)表示从顶点 v
到顶点 w有一条直接通路，即 v和 w之间存在一个关系，用顶点偶对
<v,w>来表示。
通常可以根据图的顶点偶对将图分为 有向图 和 无向图 。
A
D
E
F
C
B
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 3页有向图如下图 (a)是一个有向图 G,可形式地表示为：
G=(V,E)
V={a,b,c,d,e}
E={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}
E是 有向边（也称弧） 的有限集合，弧是顶点的有序对，记为
<v,w>,v,w是顶点,v为 弧尾,w为 弧头
b
c d
e
a
（ a) 有向图 G
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 4页无向图如图 (b)所示的是一个无向图 G，可形式地表示为：
G=(V,E)
V={a,b,c,d}
E = {(a,b),(a,c),(a,d),(b,d),(c,d)}
E(G)是边的有限集合，边是顶点的无序对，记为（ v,w）或（ w,v)，
并且（ v,w)=(w,v)
bc
d
a
(b) 无向图 G
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 5页
有向完备图 —— n个顶点的有向图最大边数是 n(n-1)
无向完备图 —— n个顶点的无向图最大边数是 n(n-1)/2
例 2
1 3
2
1 3
有向完备图 无向完备图若边或弧的个数 e<nlogn，则称作 稀疏图,否则称作 稠密图 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 6页
权 —— 与图的边或弧相关的数叫权
网 —— 带权的图叫网一个带权有向图
12
61
3
81
9
5
5
2 4
31
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 7页
子图 —— 如果图 G(V,E)和图 G‘(V’,E‘),满足：
V’?V
E’?E
则称 G‘为 G的子图
3
5
6
例
2 4 5
1 3 6
图与子图
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 8页
顶点的度
无向图中，顶点的度 TD为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度 ID：以该顶点为头的弧的数目
出度 OD：以该顶点为尾的弧的数目例
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 9页
路径 —— 路径是顶点的序列 V={Vi0,Vi1,…… Vin}，满足 (Vij-1,Vij)?E 或
<Vij-1,Vij>?E,(1<j?n)
路径长度 —— 沿路径边的数目或沿路径各边权值之和
回路 —— 第一个顶点和最后一个顶点相同的路径叫回路
简单路径 —— 序列中顶点不重复出现的路径叫 ~
简单回路 —— 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫 ~
例
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 10页
连通 —— 从顶点 V到顶点 W有一条路径，则说 V和 W是连通的
连通图 —— 图中任意两个顶点都是连通的叫 ~
连通分量 —— 非连通图的每一个连通部分叫 ~
强连通图 —— 有向图中，如果对每一对 Vi,Vj?V,Vi?Vj,从 Vi到
Vj 和从 Vj到 Vi都存在路径，则称 G是 ~
连通图例
2 4 5
1 3 6
强连通图
3
5
6
例非连通图连通分量例
2 4 5
1 3 6
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 11页图的基本操作
(1) CreateGraph(G)：图的创建操作 。
初始条件：无 。
操作结果：生成一个没有顶点的空图 G。
(2) LocateVex(G,v)：顶点定位函数 。
初始条件,G已经存在,v是一个顶点 。
操作结果：返回 v在 G中的位置,若 G中无此顶点,则返回,空,。
(3) FirstAdj(G,v)：求第一个邻接点函数 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：返回 v的第一个邻接点,若 v在 G中无邻接点,则返回
,空,。
(4) NextAdj(G,v,w)：求下一个邻接点函数 。
初始条件,G已经存在,v是 G中某个顶点,w是 v的一个邻接点 。
操作结果：返回 v的邻接点中 w之后的下一个邻接点，若无下一邻接点，则返回,空,。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 12页
(5) getVexVal(G,v)：取顶点元素值函数 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：返回 v的值 。
(6) Updatevex(G,v,e)：修改顶点元素操作 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：将 v的元素值改为 e。
(7) AddVex(G,v)：增加顶点操作 。
初始条件,G已经存在,且 G中不存在顶点 v。
操作结果：在 G中增加一个新顶点 v。
(8) deletevex(G,v)：删除顶点操作 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：从 G中删除顶点 v以及与 v相关的弧或边 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 13页
(9) AddArc(G,arc)：增加弧 （ 或边 ） 操作 。
初始条件,G已经存在,arc是一条弧 （ 或边 ） 。
操作结果：在 G中增加一条弧 （ 或边 ） arc。
(10) deleteArc(G,v,w),删除弧 （ 或边 ） 操作 。
初始条件,G已经存在,v,w是 G中的两个顶点 。
操作结果：从 G中删除弧 <v,w>,若 G为无向图,则删除边 (v,w)。
(11) destoryG(G)：撤消图操作 。
初始条件,G已经存在 。
操作结果：将图 G清除 。
(12) TraverseGraph (G,v)：遍历图操作 。
初始条件,G已经存在,v是指定的起始顶点 。
操作结果：按照某种规则将图 G的每个顶点进行遍历 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 14页
7.2 图的存储结构
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 15页
7.2.1 图的数组 (邻接矩阵 )存储表示邻接矩阵 —— 表示顶点间相联关系的矩阵定义：设 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?
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 16页
无向图的邻接矩阵对称，可压缩存储；有 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?
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 17页例 1
4
5
2
3
7
5
3
1
8
6
4
2
，其它0
E ( G )v,v或)v,(v若,],[ jijiijjiA?
06183
60240
12007
84005
30750
0624
6063
2055
465051
3506
5160
0 1 2 3 4 5
0
1
2
3
4
5
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 18页图的数组 (邻接矩阵 )存储表示
#define INFINITY INT_MAX // 最大值 ∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef enum {DG,DN,AG,AN} GraphKind;
//{有向图,有向网,无向图,无向网 }
typedef struct ArcCell {
VRType adj; // VRType是顶点关系类型。
// 对无权图，用 1或 0表示相邻否； 对带权图，则为权值类型。
InfoType *info; // 该弧相关信息的指针
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum,arcnum; // 图的当前顶点数和弧 (边 )数
GraphKind kind; // 图的种类标志
} MGraph;
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 19页图的邻接表存储表示
邻接表是图的一种链式存储结构 。
在邻接表中,对图中的每个顶点建立一个单链表,存储该顶点所有邻接点及其关系信息 。
每个单链表设一个头结点,称为顶点结点 。 单链表中的结点称为表结点,第
i个结点表示该顶点的第 i个邻接点 。
对于具有 n个顶点的图来说,其邻接表是由 n个链表组成的 。
每个链表的顶点结点包括两个域,
Vertex域存放顶点的数据信息
FirstArc域指出依附于该顶点的第一条弧 （ 或边 ） 。
表结点由三个域组成,其中
adjvex域存放相邻接顶点的位置
info域存放相应的弧或边信息 （ 包括权值 ）,对于无带权图,
如果没有与边相关的其它信息,可省略此域
NextArc域指向下一个表结点 。
Vertex FirstArc顶点结点：
Adjvex Info NextArc表结点：
例
G1
b
d
a
c
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 20页
顶点结点和表结点的结构如下所示,
Vertex FirstArc顶点结点：
Adjvex Info NextArc表结点：
例
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 ^
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 21页图的邻接表存储表示
#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]; //顶点数组
typedef struct {
AdjList vertices;
int vexnum,arcnum; // 图的当前顶点数和弧数
int kind; // 图的种类标志
} ALGraph;
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 22页
void CreateUDG(ALGraph &G)
{ // 采用邻接表存储表示，构造无向图 G（ G.kind=UDG）。
cin >> G.vexnum >> G.arcnum >> IncInfo; // IncInfo为 0表明各弧不含其它信息
for (i=0; i<G.vexnum; ++i) { // 构造表头向量
cin >> G.vertices[i].data; // 输入顶点值
G.vertices[i].firstarc = NULL; // 初始化链表头指针为 "空 "
}//for
for (k=0; k<G.arcnum; ++k) { // 输入各边并构造邻接表
cin >> v1 >> v2; // 输入一条弧的始点和终点
i = LocateVex(G,v1); j = LocateVex(G,v2);
// 确定 v1和 v2在 G中位置，即顶点的序号
pi = new ArcNode;
pi -> adjvex = j; // 对弧结点赋邻接点 "位置 "信息
pi -> nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = pi;
// 插入链表 G.vertices[i],前插
pj = new ArcNode;
pj -> adjvex = i; // 对弧结点赋邻接点 "位置 "信息
pj -> nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = pj;
// 插入链表 G.vertices[j]
if (IncInfo) // 若弧含有相关信息，则输入
{ cin>> pj->info; pi->info=pj->info; }
}//for
} // CreateUDG
算法 7.1
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 23页
7.4 图的遍历
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 24页定义
给出一个图 G和其中的任意一个顶点 v,从 v出发访问图 G中的所有顶点,且每个顶点仅访问一次,这一过程叫做 图的遍历 。
根据每个顶点在遍历过程中访问的先后顺序,
可以得到由图的所有顶点组成的序列,这个序列称为 遍历序列 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 25页
复杂性与树的遍历相比，图的遍历要复杂得多。因为图的任一顶点都可能与其余的顶点相邻接，所以在访问了某个顶点之后，在以后的访问过程中又可能沿另外某个路径绕回到先前已访问过的顶点。
解决办法为了避免重复访问图中的顶点，必须在遍历过程中对已访问的顶点进行标记。为此，可设立一个辅助数组 visited[n]，它的初始值置为,假,,一旦某个顶点 vi被访问，便将 visited[i]置为,真
” 。
遍历方式图的遍历通常有 深度优先搜索 和 广度优先搜索 两种遍历方式，它们对无向图和有向图都适用
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 26页
7.3.1 深度优先搜索
深度优先搜索 (DFS—Depth First Search)是从图的某一顶点 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? V8?V3
V6?V7?V5
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 27页
a b
c
h
d e
k
f
g
F F F F F F F F FT T T T T T T T T
a c h d k f e b g
访问标志,
访问次序,
例如,
0a 1b 2c 3d 4e 5 f 6g 7h 8k
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 28页深度优先遍历算法 --递归算法开始访问 V0,置 标志求 V0邻接点有邻接点 w
求下一邻接点w?V0
W访问过结束
N
Y
N
Y
DFS
开始标志数组初始化
Vi=1
Vi访问过
DFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 29页算法 7.2
void DFS(Graph G,int v)
{
// 从第 v个顶点出发递归地深度优先遍历图 G。
visited[v] = TRUE; VisitFunc(v); // 访问第 v个顶点
for ( w=FirstAdjVex(G,v); w!=0; w=NextAdjVex(G,v,w) )
if (!visited[w]) DFS(G,w);
// 对 v的尚未访问的邻接顶点 w递归调用 DFS
}//DFS
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 30页算法 7.3
void DFSTraverse(ALGraph G)
{
// 对以邻接表表示的图 G作深度优先遍历。
bool visited[G.vexnum]; // 附设访问标志数组
for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;
// 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) DFS(G,v);
// 对尚未访问的顶点调用 DFS
}
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 31页算法 7.4
void DFS(ALGraph G,int v)
{
// 从第 v个顶点出发递归地深度优先遍历图 G。
visited[v] = TRUE; VisitFunc(G.vertices[v].data); // 访问第 v个顶点
for ( p=G.vertices[ v ].firstarc; p; p=p->nextarc; ) {
w = p->adjvex;
if (!visited[w]) DFS(G,w);
// 对 v的尚未访问的邻接顶点 w递归调用 DFS
}
}//DFS
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 32页
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
注意：根据邻接表来决定访问次序
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 33页
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 34页
7.3.2 广度优先遍历 (BFS)
广度优先遍历 BFS— Breadth First Search方法：从图的某一顶点 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?V3?
V4?V6?V7?V8?V5
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 35页算法 7.5
void BFSTraverse(MGraph G)
{ // 对以数组存储表示的图 G进行广度优先搜索遍历。
bool visited[G.vexnum]; // 访问标志数组
SqQueue Q; // 附设循环队列 Q
for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;
InitQueue(Q,G.vexnum); // 设置空队列 Q
for ( v=0; v<G.vexnum; ++v )
if ( !visited[v]) {
visited[v] = TRUE; VisitFunc(G.vexs[v]); // 访问图中第 v个顶点
EnQueue_Sq(Q,v); // v入队列
while (!QueueEmpty_Sq(Q)) {
DeQueue_Sq(Q,u); // 队头元素出队并置为 u
for ( w=0; w<G.vexnum; w++ )
if ( G.arcs[u,w].adj && ! visited[w] ) { //和 u相邻接的点 w
visited[w] = TRUE; VisitFunc(w); // 访问图中第 w个顶点
EnQueue_Sq(Q,w); // 当前访问的顶点 w入队列 Q
} //if
} //while
} //if
} // BFSTraverse
例 1
5
3
2
4 G2
00110
00101
11010
10101
01010
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 36页开始标志数组初始化
Vi=1
Vi访问过
BFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
开始访问 V0,置 标志求 V邻接点 w
w存在吗 V下一邻接点?w
w访问过结束
N
Y
N
Y
BFS
初始化队列
V0入队队列空吗队头 V出队 访问 w,置 标志
w入队
N
a
a
Y
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 37页例 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
使用邻接表存储的图广度遍历
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 38页例 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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 39页
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 40页
7.4 连通网的 最小生成树
生成树定义,所有顶点均由边连接在一起，但不存在回路的图叫生成树
深度优先生成树 与 广度优先生成树
生成森林,非连通图每个连通分量的生成树一起组成非连通图的生成森林
说明
– 一个图可以有许多棵不同的生成树
– 所有生成树具有以下共同特点,
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 41页
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 42页例
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
深度优先生成森林
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 43页最小生成树
问题提出要在 n个城市间建立通信联络网，顶点 ——表示城市，权 ——城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 ——
最小代价生成树
问题分析
n个城市间，最多可设置 n(n-1)/2条线路,n个城市间建立通信网，只需 n-1条线路。问题转化为：如何在可能的线路中选择 n-1
条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）
最小。 1
65
43
27
13
17
9
18
12
7 5
24
10
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 44页构造最小生成树方法 一：克鲁斯卡尔 (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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 45页构造最小生成树方法 二：普里姆 (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)
由于 普里姆算法的时间复杂度为 O(n2)，则适于稠密图；而克鲁斯卡尔算法需对 e条边按权值进行排序，其时间复杂度为 O(eloge)，则适于稀疏图。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 46页例 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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 47页
7.5 单源最短路径
问题背景从某个城市出发，能否到达另外一个城市？走哪条路径花费最少？
路径可能有三种情况：
– 没有路径
– 只有一条路径（即最短路径）
– 存在多条路径（必存在一条最短路径）
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 48页数学模型
用带权的有向图表示一个交通运输网，图中：
顶点 ——表示城市边 ——表示城市间的交通联系权 ——表示此线路的长度或沿此线路运输所花的时间或费用等
问题,从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 ——最短路径
例：从某个源点到其余各顶点的最短路径
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 49页
Dijkstra算法（求最短路径）
Dijkstra算法：按路径长度递增的次序求从源点到各终点最短路径算法。
从源点到其它各终点的路径长度最短的路径中，其中最短路径的特点：
在这条路径上，必定只含一条弧，并且这条弧的权值最小 (记为 Vp） 。
b-c
v0
vp
v2
v1
vk
l1
l2
lp
lk
b
a g
c
d
e
f
20
9
10
30
18
5
10
8
15
12
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 50页
下一条路径长度次短的最短路径的特点,（ vq)
它只可能有两种情况：
或者是直接从源点到该点 (只含一条弧 )；
或者是从源点经过顶点 vp，再到达该顶点 (由两条弧组成 )。
再下一条路径长度次短的最短路径的特点,
它可能有三种情况：
或者是直接从源点到该点 (只含一条弧 )；
或者是从源点经过顶点 vP，再到达该顶点 (由两条弧组成 )；
或者是从源点经过顶点 vq，再到达该顶点。
其余最短路径的特点：
它或者是直接从源点到该点 (只含一条弧 )； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。
b-c
b-c-e
b-a
…
b
a g
c
d
e
f
20
9
10
30
18
5
10
8
15
12
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 51页图的存储,以 1~n 分别代表 n个顶点,采用邻接矩阵存储该图,有
Wij 当顶点 vi 到顶点 vj 有边,且权为 Wij
AS[i,j]=? 当顶点 vi 到顶点 vj无边时
0 当 vi=vj 时?
b
a g
c
d
e
f
20
9
10
30
18
5
10
8
15
12
0 ∞ ∞ ∞ ∞ ∞ 9
20 0 10 30 ∞ ∞ ∞
∞ ∞ 0 ∞ ∞ ∞ ∞
∞ ∞ ∞ 0 ∞ ∞ ∞
∞ ∞ ∞ 12 0 ∞ 15
∞ ∞ ∞ ∞ 8 0 10
∞ ∞ 18 ∞ ∞ ∞ 0
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 52页求最短路径的迪杰斯特拉算法,
AS[n][n]网的邻接矩阵,S为已找到最短路径的终点的集合，辅助数组
Dist，其中每个分量 Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。
(1)初始状态：
Disk[k]=AS[i,k] i为源点在图中的序号
S={源点 Vi}
(2)选择 u
Disk[u]=min{Disk[w]|w∈S,w ∈V(G)}
顶点 u并入集合 S(找到一个 )
(3)修改数组 Disk中所有尚未找到的最短路径的终点的对应分量值。如果 AS [u,w]为有限值，及从顶点 u到顶点ｗ有弧存在，并且
Disk[u]+ AS[u,w]< Disk[w]
则令
Disk[w]= Disk[w]+ AS[u,w]
(4)重复上述步骤 (2)(3)操作 n-1次,即可求得从源点到所有终点的最短路径
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 53页
24
15
8
6
3
9
7
3
5
10
4
a
f
e
d
b
c g2
0 24 8 15
0 6
0? 7 3?
0 4
0? 9
5 2 0 10
3 0
a
b
c
d
e
f
g
i 0 1 2 3 4 5 6 S
dist[i]
path[i]
顶点 a 为源点，设定 dist和 path的初始值，顶点 a 并入集合 S
24
ab
8
ac
15
ad
选出 dist 中的最小值在 i=2，求得第一条最短路径 {ac},顶点 c 并入集合 S
a c
考察从顶点 c 出发的弧，修正集合
V-S中顶点的 dist 和 path 的值
15
ace
11
acf
中的最小值在 5，求得第 2
条最短路径 {acf},顶点 f 并入集合 S
acf
f
考察从顶点 f 出发的弧，修正集合 V-S
中顶点的 dist 和 path 的值
13
acfe
21
acfg
中的最小值在 4，求得第 3
条最短路径 e},顶点 e 并入集合 S
ac
e
考察从顶点 e 出发的弧，修正集合 -
中顶点的 和中的最小值在 3，求得第 4
条最短路径 ad},顶点 d 并入集合
d
考察从顶点 d 出发的弧，修正集合 S
中顶点的 和
19
dg
中的最小值在 6，求得第 5
条最短路径 g},顶点 g并入集合
ad g
考察从顶点 g 出发的弧，修正集合中顶点的 和
22
adgb
选出 dist 中的最小值在 i=1，求得第 6
条最短路径 {adgb,顶点 b并入集合 S
badgb
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 54页
7.6 拓扑排序
以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为活动顶点网络（ AOV网,Activity on
vertex）。
例 1
筹备验收招标备料进驻工地测量 挖地基浇注水泥
… 验收招标备料进驻测量浇注水泥搭架子
…
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 55页程序语言数据结构离散数学软件工程操作系统编译原理数据库计算机组成汇编网络数字逻辑计算机导论例 2
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 56页
在 AOV网中，若顶点 i 到顶点 j 之间有有向路径，则称顶点 i 为顶点 j 的前驱，顶点 j 为顶点 i的后继；若顶点 i
到顶点 j 之间为一条有向边，则称顶点 i 为顶点 j 的直接前驱，顶点 j 为顶点 i 的直接后继。
在 AOV网中不允许有回路。否则为死锁现象。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 57页拓扑排序
检查 AOV网是否存在回路的方法是对 AOV网进行拓扑排序，构造一个序列，使得该序列满足条件：
1,若在 AOV网中，顶点 i 优先于顶点 j,则在该序列中也是顶点 i 优先于顶点 j 。
2,若在 AOV网中，顶点 i 与顶点 j之间不存在优先关系,
则在该序列中建立它们的优先关系，即顶点 i优先于顶点 j，
或顶点 j 优先于顶点 i 。
3,若能够构造出拓扑序列，则拓扑序列包含 AOV网的全部顶点。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 58页
v1 v5 v7v3v6 v2 v4
例
v4
v3
v2
v6
v7
v4
v3
v2
v6
v5
v7
v4
v3
v2
v7
v4
v3 v7 v7
v4
v7
v1
v4
v3
v2
v6
v5
v7
拓扑排序的方法
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 59页
7.7 关键路径例筹备付款签合同做预置件验收施工
…
招标
7天联系材料
8天图纸设计
15天进驻工地
4天运材料
6天搬运
3
天
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 60页
AOE网的定义
AOE网为一个带权的有向无环图，其中，顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 61页
正常情况下,AOE网中只有一个入度为 0 的顶点，称之为源点；有一个出度为 0 的顶点，称之为终点。
AOE网的特点：
1.只有在某个顶点所代表的事件发生以后,该顶点引发的活动才能开始。
2.进入某事件的所有边所代表的活动都已完成,该顶点所代表的事件才能发生。
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 62页关键路径
关键路径的定义从源点到终点的路径中具有最大路径长度的路径为 关键路径 ;关键路径上的活动称为 关键活动 。
关键路径的特点
– 关键路径的长度 (路径上的边的权值之和 )为完成整个工程所需要的最短时间。
– 关键路径的长度变化 (即任意关键活动的权值变化 )
将影响整个工程的进度，而其他非关键活动在一定范围内的变化不会影响工期。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 63页求关键活动的步骤
1.计算事件 j的最早发生时间 ve(j)
所谓事件 j的最早发生时间 ve(j)是指从源点到顶点 j的最大路径长度,
计算方法,
ve(1) = 0
ve(j) = MAX{ ve(i) + <i,j>的权 }
<i,j>?P( j )
j
ve(j),
1 2 3 4 5 6 7 8 9
0 6 4 5 7 7 15 14 18
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4 关键路径的长度为 18个时间单位 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 64页
2,计算事件 i的最迟发生时间 vl (i)
所谓事件 i 的最迟发生时间 vl(i)是指不影响整个工期的前提下事件 i 必须发生的最晚时间。
计算方法,
vl (n) = ve(n) i=n
vl (i) = MIN{vl(j) – <i,j>的权 } i=n-1,…,2,1
<i,j>?S(k)
<k,j>?S(k)
i
1 2 3 4 5 6 7 8 9
vl(k),1814161078660
ve(j),
1 2 3 4 5 6 7 8 9
0 6 4 5 7 7 15 14 18
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 65页
3,计算活动 k的最早开始时间 ee(k)
所谓活动 k的最早开始时间 ee(k) 是事件 i发生的最早时间，即只有事件 i 发生了，活动 k 才能开始。
计算方法,ee(k) = ve(i) k=1,2,3,…,m
活动 ki j
1 2 3 4 5 6 7 8 9 10 11
ee(i),0 0 0 6 4 5 7 7 7 15 14
1 2 3 4 5 6 7 8 9
0 6 4 5 7 7 15 14 18
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
ve(j),
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 66页
4,计算活动 k 的最迟开始时间 el(k)
所谓活动 k 的最迟开始时间 el(k) 是指不推迟整个工期的前提下活动 k开始的最晚时间。
计算方法,el(k) = vl(j) -<i,j>的权 k=1,2,3,…,m
活动 ki j
1 2 3 4 5 6 7 8 9 10 11
el(i),0 2 3 6 6 8 78 10 16 14
1 2 3 4 5 6 7 8 9
vl(k),1814161078660
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 67页
5,求出关键活动与关键路径
计算方法,el(i) -ee(i)=?
1 2 3 4 5 6 7 8 9 10 11
el(i),0 2 3 6 6 8 78 10 16 14
1 2 3 4 5 6 7 8 9 10 11
ee(i),0 0 0 6 4 5 7 7 7 15 14
1 2 3 4 5 6 7 8 9 10 11
0 2 3 0 2 3 1 0 3 1 0
a1 a4 a8 a11
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 1页第 7章 图和广义表
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 2页
7.1 图的定义和基本术语
图 (Graph)G是由两个集合 V和 E组成的偶对,表示为
G=（ V,E）
其中 V是有限非空的顶点集合,E是由顶点偶对表示的关系集合。
为了讨论方便，有时也将顶点集合为空的图称为空图。
一个图可以形式化定义为：
G=（ V,E）
V={v|v?data object}
E={<v,w>| v,w?V∧P(v,w)}
其中 v是数据元素，称为 顶点 （ vertex）,P(v,w)表示从顶点 v
到顶点 w有一条直接通路，即 v和 w之间存在一个关系，用顶点偶对
<v,w>来表示。
通常可以根据图的顶点偶对将图分为 有向图 和 无向图 。
A
D
E
F
C
B
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 3页有向图如下图 (a)是一个有向图 G,可形式地表示为：
G=(V,E)
V={a,b,c,d,e}
E={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>}
E是 有向边（也称弧） 的有限集合，弧是顶点的有序对，记为
<v,w>,v,w是顶点,v为 弧尾,w为 弧头
b
c d
e
a
（ a) 有向图 G
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 4页无向图如图 (b)所示的是一个无向图 G，可形式地表示为：
G=(V,E)
V={a,b,c,d}
E = {(a,b),(a,c),(a,d),(b,d),(c,d)}
E(G)是边的有限集合，边是顶点的无序对，记为（ v,w）或（ w,v)，
并且（ v,w)=(w,v)
bc
d
a
(b) 无向图 G
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 5页
有向完备图 —— n个顶点的有向图最大边数是 n(n-1)
无向完备图 —— n个顶点的无向图最大边数是 n(n-1)/2
例 2
1 3
2
1 3
有向完备图 无向完备图若边或弧的个数 e<nlogn，则称作 稀疏图,否则称作 稠密图 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 6页
权 —— 与图的边或弧相关的数叫权
网 —— 带权的图叫网一个带权有向图
12
61
3
81
9
5
5
2 4
31
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 7页
子图 —— 如果图 G(V,E)和图 G‘(V’,E‘),满足：
V’?V
E’?E
则称 G‘为 G的子图
3
5
6
例
2 4 5
1 3 6
图与子图
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 8页
顶点的度
无向图中，顶点的度 TD为与每个顶点相连的边数
有向图中，顶点的度分成入度与出度
入度 ID：以该顶点为头的弧的数目
出度 OD：以该顶点为尾的弧的数目例
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 9页
路径 —— 路径是顶点的序列 V={Vi0,Vi1,…… Vin}，满足 (Vij-1,Vij)?E 或
<Vij-1,Vij>?E,(1<j?n)
路径长度 —— 沿路径边的数目或沿路径各边权值之和
回路 —— 第一个顶点和最后一个顶点相同的路径叫回路
简单路径 —— 序列中顶点不重复出现的路径叫 ~
简单回路 —— 除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫 ~
例
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 10页
连通 —— 从顶点 V到顶点 W有一条路径，则说 V和 W是连通的
连通图 —— 图中任意两个顶点都是连通的叫 ~
连通分量 —— 非连通图的每一个连通部分叫 ~
强连通图 —— 有向图中，如果对每一对 Vi,Vj?V,Vi?Vj,从 Vi到
Vj 和从 Vj到 Vi都存在路径，则称 G是 ~
连通图例
2 4 5
1 3 6
强连通图
3
5
6
例非连通图连通分量例
2 4 5
1 3 6
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 11页图的基本操作
(1) CreateGraph(G)：图的创建操作 。
初始条件：无 。
操作结果：生成一个没有顶点的空图 G。
(2) LocateVex(G,v)：顶点定位函数 。
初始条件,G已经存在,v是一个顶点 。
操作结果：返回 v在 G中的位置,若 G中无此顶点,则返回,空,。
(3) FirstAdj(G,v)：求第一个邻接点函数 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：返回 v的第一个邻接点,若 v在 G中无邻接点,则返回
,空,。
(4) NextAdj(G,v,w)：求下一个邻接点函数 。
初始条件,G已经存在,v是 G中某个顶点,w是 v的一个邻接点 。
操作结果：返回 v的邻接点中 w之后的下一个邻接点，若无下一邻接点，则返回,空,。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 12页
(5) getVexVal(G,v)：取顶点元素值函数 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：返回 v的值 。
(6) Updatevex(G,v,e)：修改顶点元素操作 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：将 v的元素值改为 e。
(7) AddVex(G,v)：增加顶点操作 。
初始条件,G已经存在,且 G中不存在顶点 v。
操作结果：在 G中增加一个新顶点 v。
(8) deletevex(G,v)：删除顶点操作 。
初始条件,G已经存在,v是 G中某个顶点 。
操作结果：从 G中删除顶点 v以及与 v相关的弧或边 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 13页
(9) AddArc(G,arc)：增加弧 （ 或边 ） 操作 。
初始条件,G已经存在,arc是一条弧 （ 或边 ） 。
操作结果：在 G中增加一条弧 （ 或边 ） arc。
(10) deleteArc(G,v,w),删除弧 （ 或边 ） 操作 。
初始条件,G已经存在,v,w是 G中的两个顶点 。
操作结果：从 G中删除弧 <v,w>,若 G为无向图,则删除边 (v,w)。
(11) destoryG(G)：撤消图操作 。
初始条件,G已经存在 。
操作结果：将图 G清除 。
(12) TraverseGraph (G,v)：遍历图操作 。
初始条件,G已经存在,v是指定的起始顶点 。
操作结果：按照某种规则将图 G的每个顶点进行遍历 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 14页
7.2 图的存储结构
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 15页
7.2.1 图的数组 (邻接矩阵 )存储表示邻接矩阵 —— 表示顶点间相联关系的矩阵定义：设 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?
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 16页
无向图的邻接矩阵对称，可压缩存储；有 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?
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 17页例 1
4
5
2
3
7
5
3
1
8
6
4
2
，其它0
E ( G )v,v或)v,(v若,],[ jijiijjiA?
06183
60240
12007
84005
30750
0624
6063
2055
465051
3506
5160
0 1 2 3 4 5
0
1
2
3
4
5
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 18页图的数组 (邻接矩阵 )存储表示
#define INFINITY INT_MAX // 最大值 ∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef enum {DG,DN,AG,AN} GraphKind;
//{有向图,有向网,无向图,无向网 }
typedef struct ArcCell {
VRType adj; // VRType是顶点关系类型。
// 对无权图，用 1或 0表示相邻否； 对带权图，则为权值类型。
InfoType *info; // 该弧相关信息的指针
} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
AdjMatrix arcs; // 邻接矩阵
int vexnum,arcnum; // 图的当前顶点数和弧 (边 )数
GraphKind kind; // 图的种类标志
} MGraph;
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 19页图的邻接表存储表示
邻接表是图的一种链式存储结构 。
在邻接表中,对图中的每个顶点建立一个单链表,存储该顶点所有邻接点及其关系信息 。
每个单链表设一个头结点,称为顶点结点 。 单链表中的结点称为表结点,第
i个结点表示该顶点的第 i个邻接点 。
对于具有 n个顶点的图来说,其邻接表是由 n个链表组成的 。
每个链表的顶点结点包括两个域,
Vertex域存放顶点的数据信息
FirstArc域指出依附于该顶点的第一条弧 （ 或边 ） 。
表结点由三个域组成,其中
adjvex域存放相邻接顶点的位置
info域存放相应的弧或边信息 （ 包括权值 ）,对于无带权图,
如果没有与边相关的其它信息,可省略此域
NextArc域指向下一个表结点 。
Vertex FirstArc顶点结点：
Adjvex Info NextArc表结点：
例
G1
b
d
a
c
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 20页
顶点结点和表结点的结构如下所示,
Vertex FirstArc顶点结点：
Adjvex Info NextArc表结点：
例
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 ^
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 21页图的邻接表存储表示
#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]; //顶点数组
typedef struct {
AdjList vertices;
int vexnum,arcnum; // 图的当前顶点数和弧数
int kind; // 图的种类标志
} ALGraph;
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 22页
void CreateUDG(ALGraph &G)
{ // 采用邻接表存储表示，构造无向图 G（ G.kind=UDG）。
cin >> G.vexnum >> G.arcnum >> IncInfo; // IncInfo为 0表明各弧不含其它信息
for (i=0; i<G.vexnum; ++i) { // 构造表头向量
cin >> G.vertices[i].data; // 输入顶点值
G.vertices[i].firstarc = NULL; // 初始化链表头指针为 "空 "
}//for
for (k=0; k<G.arcnum; ++k) { // 输入各边并构造邻接表
cin >> v1 >> v2; // 输入一条弧的始点和终点
i = LocateVex(G,v1); j = LocateVex(G,v2);
// 确定 v1和 v2在 G中位置，即顶点的序号
pi = new ArcNode;
pi -> adjvex = j; // 对弧结点赋邻接点 "位置 "信息
pi -> nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = pi;
// 插入链表 G.vertices[i],前插
pj = new ArcNode;
pj -> adjvex = i; // 对弧结点赋邻接点 "位置 "信息
pj -> nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = pj;
// 插入链表 G.vertices[j]
if (IncInfo) // 若弧含有相关信息，则输入
{ cin>> pj->info; pi->info=pj->info; }
}//for
} // CreateUDG
算法 7.1
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 23页
7.4 图的遍历
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 24页定义
给出一个图 G和其中的任意一个顶点 v,从 v出发访问图 G中的所有顶点,且每个顶点仅访问一次,这一过程叫做 图的遍历 。
根据每个顶点在遍历过程中访问的先后顺序,
可以得到由图的所有顶点组成的序列,这个序列称为 遍历序列 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 25页
复杂性与树的遍历相比，图的遍历要复杂得多。因为图的任一顶点都可能与其余的顶点相邻接，所以在访问了某个顶点之后，在以后的访问过程中又可能沿另外某个路径绕回到先前已访问过的顶点。
解决办法为了避免重复访问图中的顶点，必须在遍历过程中对已访问的顶点进行标记。为此，可设立一个辅助数组 visited[n]，它的初始值置为,假,,一旦某个顶点 vi被访问，便将 visited[i]置为,真
” 。
遍历方式图的遍历通常有 深度优先搜索 和 广度优先搜索 两种遍历方式，它们对无向图和有向图都适用
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 26页
7.3.1 深度优先搜索
深度优先搜索 (DFS—Depth First Search)是从图的某一顶点 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? V8?V3
V6?V7?V5
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 27页
a b
c
h
d e
k
f
g
F F F F F F F F FT T T T T T T T T
a c h d k f e b g
访问标志,
访问次序,
例如,
0a 1b 2c 3d 4e 5 f 6g 7h 8k
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 28页深度优先遍历算法 --递归算法开始访问 V0,置 标志求 V0邻接点有邻接点 w
求下一邻接点w?V0
W访问过结束
N
Y
N
Y
DFS
开始标志数组初始化
Vi=1
Vi访问过
DFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 29页算法 7.2
void DFS(Graph G,int v)
{
// 从第 v个顶点出发递归地深度优先遍历图 G。
visited[v] = TRUE; VisitFunc(v); // 访问第 v个顶点
for ( w=FirstAdjVex(G,v); w!=0; w=NextAdjVex(G,v,w) )
if (!visited[w]) DFS(G,w);
// 对 v的尚未访问的邻接顶点 w递归调用 DFS
}//DFS
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 30页算法 7.3
void DFSTraverse(ALGraph G)
{
// 对以邻接表表示的图 G作深度优先遍历。
bool visited[G.vexnum]; // 附设访问标志数组
for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;
// 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) DFS(G,v);
// 对尚未访问的顶点调用 DFS
}
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 31页算法 7.4
void DFS(ALGraph G,int v)
{
// 从第 v个顶点出发递归地深度优先遍历图 G。
visited[v] = TRUE; VisitFunc(G.vertices[v].data); // 访问第 v个顶点
for ( p=G.vertices[ v ].firstarc; p; p=p->nextarc; ) {
w = p->adjvex;
if (!visited[w]) DFS(G,w);
// 对 v的尚未访问的邻接顶点 w递归调用 DFS
}
}//DFS
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 32页
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
注意：根据邻接表来决定访问次序
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 33页
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 34页
7.3.2 广度优先遍历 (BFS)
广度优先遍历 BFS— Breadth First Search方法：从图的某一顶点 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?V3?
V4?V6?V7?V8?V5
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 35页算法 7.5
void BFSTraverse(MGraph G)
{ // 对以数组存储表示的图 G进行广度优先搜索遍历。
bool visited[G.vexnum]; // 访问标志数组
SqQueue Q; // 附设循环队列 Q
for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;
InitQueue(Q,G.vexnum); // 设置空队列 Q
for ( v=0; v<G.vexnum; ++v )
if ( !visited[v]) {
visited[v] = TRUE; VisitFunc(G.vexs[v]); // 访问图中第 v个顶点
EnQueue_Sq(Q,v); // v入队列
while (!QueueEmpty_Sq(Q)) {
DeQueue_Sq(Q,u); // 队头元素出队并置为 u
for ( w=0; w<G.vexnum; w++ )
if ( G.arcs[u,w].adj && ! visited[w] ) { //和 u相邻接的点 w
visited[w] = TRUE; VisitFunc(w); // 访问图中第 w个顶点
EnQueue_Sq(Q,w); // 当前访问的顶点 w入队列 Q
} //if
} //while
} //if
} // BFSTraverse
例 1
5
3
2
4 G2
00110
00101
11010
10101
01010
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 36页开始标志数组初始化
Vi=1
Vi访问过
BFS
Vi=Vi+1
Vi==Vexnums
结束
N
N
Y
Y
开始访问 V0,置 标志求 V邻接点 w
w存在吗 V下一邻接点?w
w访问过结束
N
Y
N
Y
BFS
初始化队列
V0入队队列空吗队头 V出队 访问 w,置 标志
w入队
N
a
a
Y
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 37页例 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
使用邻接表存储的图广度遍历
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 38页例 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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 39页
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 40页
7.4 连通网的 最小生成树
生成树定义,所有顶点均由边连接在一起，但不存在回路的图叫生成树
深度优先生成树 与 广度优先生成树
生成森林,非连通图每个连通分量的生成树一起组成非连通图的生成森林
说明
– 一个图可以有许多棵不同的生成树
– 所有生成树具有以下共同特点,
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图
一个有 n个顶点的连通图的生成树有 n-1条边
生成树中任意两个顶点间的路径是唯一的
在生成树中再加一条边必然形成回路
含 n个顶点 n-1条边的图不一定是生成树
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 41页
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 42页例
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
深度优先生成森林
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 43页最小生成树
问题提出要在 n个城市间建立通信联络网，顶点 ——表示城市，权 ——城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小 ——
最小代价生成树
问题分析
n个城市间，最多可设置 n(n-1)/2条线路,n个城市间建立通信网，只需 n-1条线路。问题转化为：如何在可能的线路中选择 n-1
条，能把所有城市（顶点）均连起来，且总耗费各边权值之和）
最小。 1
65
43
27
13
17
9
18
12
7 5
24
10
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 44页构造最小生成树方法 一：克鲁斯卡尔 (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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 45页构造最小生成树方法 二：普里姆 (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)
由于 普里姆算法的时间复杂度为 O(n2)，则适于稠密图；而克鲁斯卡尔算法需对 e条边按权值进行排序，其时间复杂度为 O(eloge)，则适于稀疏图。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 46页例 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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 47页
7.5 单源最短路径
问题背景从某个城市出发，能否到达另外一个城市？走哪条路径花费最少？
路径可能有三种情况：
– 没有路径
– 只有一条路径（即最短路径）
– 存在多条路径（必存在一条最短路径）
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 48页数学模型
用带权的有向图表示一个交通运输网，图中：
顶点 ——表示城市边 ——表示城市间的交通联系权 ——表示此线路的长度或沿此线路运输所花的时间或费用等
问题,从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 ——最短路径
例：从某个源点到其余各顶点的最短路径
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
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 49页
Dijkstra算法（求最短路径）
Dijkstra算法：按路径长度递增的次序求从源点到各终点最短路径算法。
从源点到其它各终点的路径长度最短的路径中，其中最短路径的特点：
在这条路径上，必定只含一条弧，并且这条弧的权值最小 (记为 Vp） 。
b-c
v0
vp
v2
v1
vk
l1
l2
lp
lk
b
a g
c
d
e
f
20
9
10
30
18
5
10
8
15
12
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 50页
下一条路径长度次短的最短路径的特点,（ vq)
它只可能有两种情况：
或者是直接从源点到该点 (只含一条弧 )；
或者是从源点经过顶点 vp，再到达该顶点 (由两条弧组成 )。
再下一条路径长度次短的最短路径的特点,
它可能有三种情况：
或者是直接从源点到该点 (只含一条弧 )；
或者是从源点经过顶点 vP，再到达该顶点 (由两条弧组成 )；
或者是从源点经过顶点 vq，再到达该顶点。
其余最短路径的特点：
它或者是直接从源点到该点 (只含一条弧 )； 或者是从源点经过已求得最短路径的顶点，再到达该顶点。
b-c
b-c-e
b-a
…
b
a g
c
d
e
f
20
9
10
30
18
5
10
8
15
12
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 51页图的存储,以 1~n 分别代表 n个顶点,采用邻接矩阵存储该图,有
Wij 当顶点 vi 到顶点 vj 有边,且权为 Wij
AS[i,j]=? 当顶点 vi 到顶点 vj无边时
0 当 vi=vj 时?
b
a g
c
d
e
f
20
9
10
30
18
5
10
8
15
12
0 ∞ ∞ ∞ ∞ ∞ 9
20 0 10 30 ∞ ∞ ∞
∞ ∞ 0 ∞ ∞ ∞ ∞
∞ ∞ ∞ 0 ∞ ∞ ∞
∞ ∞ ∞ 12 0 ∞ 15
∞ ∞ ∞ ∞ 8 0 10
∞ ∞ 18 ∞ ∞ ∞ 0
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 52页求最短路径的迪杰斯特拉算法,
AS[n][n]网的邻接矩阵,S为已找到最短路径的终点的集合，辅助数组
Dist，其中每个分量 Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。
(1)初始状态：
Disk[k]=AS[i,k] i为源点在图中的序号
S={源点 Vi}
(2)选择 u
Disk[u]=min{Disk[w]|w∈S,w ∈V(G)}
顶点 u并入集合 S(找到一个 )
(3)修改数组 Disk中所有尚未找到的最短路径的终点的对应分量值。如果 AS [u,w]为有限值，及从顶点 u到顶点ｗ有弧存在，并且
Disk[u]+ AS[u,w]< Disk[w]
则令
Disk[w]= Disk[w]+ AS[u,w]
(4)重复上述步骤 (2)(3)操作 n-1次,即可求得从源点到所有终点的最短路径
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 53页
24
15
8
6
3
9
7
3
5
10
4
a
f
e
d
b
c g2
0 24 8 15
0 6
0? 7 3?
0 4
0? 9
5 2 0 10
3 0
a
b
c
d
e
f
g
i 0 1 2 3 4 5 6 S
dist[i]
path[i]
顶点 a 为源点，设定 dist和 path的初始值，顶点 a 并入集合 S
24
ab
8
ac
15
ad
选出 dist 中的最小值在 i=2，求得第一条最短路径 {ac},顶点 c 并入集合 S
a c
考察从顶点 c 出发的弧，修正集合
V-S中顶点的 dist 和 path 的值
15
ace
11
acf
中的最小值在 5，求得第 2
条最短路径 {acf},顶点 f 并入集合 S
acf
f
考察从顶点 f 出发的弧，修正集合 V-S
中顶点的 dist 和 path 的值
13
acfe
21
acfg
中的最小值在 4，求得第 3
条最短路径 e},顶点 e 并入集合 S
ac
e
考察从顶点 e 出发的弧，修正集合 -
中顶点的 和中的最小值在 3，求得第 4
条最短路径 ad},顶点 d 并入集合
d
考察从顶点 d 出发的弧，修正集合 S
中顶点的 和
19
dg
中的最小值在 6，求得第 5
条最短路径 g},顶点 g并入集合
ad g
考察从顶点 g 出发的弧，修正集合中顶点的 和
22
adgb
选出 dist 中的最小值在 i=1，求得第 6
条最短路径 {adgb,顶点 b并入集合 S
badgb
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 54页
7.6 拓扑排序
以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为活动顶点网络（ AOV网,Activity on
vertex）。
例 1
筹备验收招标备料进驻工地测量 挖地基浇注水泥
… 验收招标备料进驻测量浇注水泥搭架子
…
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 55页程序语言数据结构离散数学软件工程操作系统编译原理数据库计算机组成汇编网络数字逻辑计算机导论例 2
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 56页
在 AOV网中，若顶点 i 到顶点 j 之间有有向路径，则称顶点 i 为顶点 j 的前驱，顶点 j 为顶点 i的后继；若顶点 i
到顶点 j 之间为一条有向边，则称顶点 i 为顶点 j 的直接前驱，顶点 j 为顶点 i 的直接后继。
在 AOV网中不允许有回路。否则为死锁现象。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 57页拓扑排序
检查 AOV网是否存在回路的方法是对 AOV网进行拓扑排序，构造一个序列，使得该序列满足条件：
1,若在 AOV网中，顶点 i 优先于顶点 j,则在该序列中也是顶点 i 优先于顶点 j 。
2,若在 AOV网中，顶点 i 与顶点 j之间不存在优先关系,
则在该序列中建立它们的优先关系，即顶点 i优先于顶点 j，
或顶点 j 优先于顶点 i 。
3,若能够构造出拓扑序列，则拓扑序列包含 AOV网的全部顶点。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 58页
v1 v5 v7v3v6 v2 v4
例
v4
v3
v2
v6
v7
v4
v3
v2
v6
v5
v7
v4
v3
v2
v7
v4
v3 v7 v7
v4
v7
v1
v4
v3
v2
v6
v5
v7
拓扑排序的方法
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 59页
7.7 关键路径例筹备付款签合同做预置件验收施工
…
招标
7天联系材料
8天图纸设计
15天进驻工地
4天运材料
6天搬运
3
天
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 60页
AOE网的定义
AOE网为一个带权的有向无环图，其中，顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 61页
正常情况下,AOE网中只有一个入度为 0 的顶点，称之为源点；有一个出度为 0 的顶点，称之为终点。
AOE网的特点：
1.只有在某个顶点所代表的事件发生以后,该顶点引发的活动才能开始。
2.进入某事件的所有边所代表的活动都已完成,该顶点所代表的事件才能发生。
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 62页关键路径
关键路径的定义从源点到终点的路径中具有最大路径长度的路径为 关键路径 ;关键路径上的活动称为 关键活动 。
关键路径的特点
– 关键路径的长度 (路径上的边的权值之和 )为完成整个工程所需要的最短时间。
– 关键路径的长度变化 (即任意关键活动的权值变化 )
将影响整个工程的进度，而其他非关键活动在一定范围内的变化不会影响工期。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 63页求关键活动的步骤
1.计算事件 j的最早发生时间 ve(j)
所谓事件 j的最早发生时间 ve(j)是指从源点到顶点 j的最大路径长度,
计算方法,
ve(1) = 0
ve(j) = MAX{ ve(i) + <i,j>的权 }
<i,j>?P( j )
j
ve(j),
1 2 3 4 5 6 7 8 9
0 6 4 5 7 7 15 14 18
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4 关键路径的长度为 18个时间单位 。
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 64页
2,计算事件 i的最迟发生时间 vl (i)
所谓事件 i 的最迟发生时间 vl(i)是指不影响整个工期的前提下事件 i 必须发生的最晚时间。
计算方法,
vl (n) = ve(n) i=n
vl (i) = MIN{vl(j) – <i,j>的权 } i=n-1,…,2,1
<i,j>?S(k)
<k,j>?S(k)
i
1 2 3 4 5 6 7 8 9
vl(k),1814161078660
ve(j),
1 2 3 4 5 6 7 8 9
0 6 4 5 7 7 15 14 18
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 65页
3,计算活动 k的最早开始时间 ee(k)
所谓活动 k的最早开始时间 ee(k) 是事件 i发生的最早时间，即只有事件 i 发生了，活动 k 才能开始。
计算方法,ee(k) = ve(i) k=1,2,3,…,m
活动 ki j
1 2 3 4 5 6 7 8 9 10 11
ee(i),0 0 0 6 4 5 7 7 7 15 14
1 2 3 4 5 6 7 8 9
0 6 4 5 7 7 15 14 18
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
ve(j),
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 66页
4,计算活动 k 的最迟开始时间 el(k)
所谓活动 k 的最迟开始时间 el(k) 是指不推迟整个工期的前提下活动 k开始的最晚时间。
计算方法,el(k) = vl(j) -<i,j>的权 k=1,2,3,…,m
活动 ki j
1 2 3 4 5 6 7 8 9 10 11
el(i),0 2 3 6 6 8 78 10 16 14
1 2 3 4 5 6 7 8 9
vl(k),1814161078660
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
Da
ta
Str
uc
tur
e
数据结构——
第
7
章图和广义表胡建华 2009-7-24计算机教研室第 67页
5,求出关键活动与关键路径
计算方法,el(i) -ee(i)=?
1 2 3 4 5 6 7 8 9 10 11
el(i),0 2 3 6 6 8 78 10 16 14
1 2 3 4 5 6 7 8 9 10 11
ee(i),0 0 0 6 4 5 7 7 7 15 14
1 2 3 4 5 6 7 8 9 10 11
0 2 3 0 2 3 1 0 3 1 0
a1 a4 a8 a11
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
8
7
2
4
4
