1
第 7章 图和广义表
2
图（ Graph） 是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，即每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素 之间有着明显的层次关系，虽然每一层上的数据元素可能和下一层中多个元素（孩子） 相关，但只能和上一层中一个元素（双亲）
相关；而在 图形结构中，结点之间 的关系可以是任意的，任意两个数据元素之间都可能相关。
图在各个领域都有着广泛的应用,如电路网络分析、交通运输、
管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题，它们必须用图的有关方法进行处理；另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多实际问题，如果间接地用图来表示，处理起来比较方便。这些技术领域都是把图作为解决问题的主要数学手段来使用，因此，如何在计算机中表示和处理图结构，就是计算机科学需研究的一项重要课题。
3
【 学习目标 】
1．领会图的类型定义,
2．熟悉图的各种存储结构及其构造算法,
了解各种存储结构的特点和选用原则,
3．熟练掌握图的两种遍历算法,
4．理解各种图的应用问题的算法,
5.了解广义表的结构和使用
4
【 重点和难点 】
图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法 及其 应用场合 。
【 知识点 】
图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、
无向网的最小生成树、最短路径、拓扑排序、关键路径
5
第七章 习题
基础知识
–P47,7.1 7.5 7.7 7.9 7.10 7.11
作业
–P49,7.22 7.23 7.24 7.28 7.32
–P50,7.36 7.41
6
7.1 图的定义和术语
7.2 图的存储结构
7.3 图的遍历
7.4 连通网的最小生成树
7.5 单源最短路径
7.6 拓扑排序
7.7 关键路径
7.8 广义表
7
7.1 图的基本术语图,记为 G＝ ( V,E )
其中,V 是 G的顶点集合，是有穷非空集；
E 是 G的边 集合，是有穷集。
问：当 E(G)为空时，图 G存在否？
答：还存在！但此时图 G只有顶点而没有边。
有向图：
无向图：
完全图：
图 G中的每条边都是有方向的；
图 G中的每条边都是无方向的；
图 G任意两个顶点都有一条边相连接；
若 n 个顶点的无向图有 n(n-1)/2 条边,称为 无向完全图
若 n 个顶点的有向图有 n(n-1) 条边,称为 有向完全图
V=vertex
E=edge
8
② 完全有向图有 n(n-1)条边。
证明,若是完全有向图，则顶点 1必必与所有其他顶点各有 2条连线，即有 2(n-1)条边,顶点 2有 2(n-2)条边,…,顶点 n-1有 2
条边,顶点 n有 0条边,
总边数＝ 2( n-1＋ n-2＋ … ＋ 1＋ 0)=2(n-1+0)n/2= n(n-1)
① 完全无向图有 n(n-1)/2 条边。
证明,若是完全无向图，则顶点 1必与所有其他顶点各有 1条连线，即有 n-1条边，顶点 2有 n-2条边,…,顶点 n-1有 1条边,顶点
n有 0条边,
总边数＝ n-1＋ n-2＋ … ＋ 1＋ 0=（ n-1+0)n/2= n(n-1)/2
9
例：判断下列 4种图形各属什么类型？
无向 无向图 (树 ) 有向图 有向
n(n-1)/2 条边 n(n-1) 条边
G1的顶点集合为 V(G1)={0,1,2,3}
边集合为 E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
完全图 完全图
10
例
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)}
11
稀疏图：
稠密图：
设有两个图 G＝ (V,E) 和 G’＝ (V’,E’)。若 V’? V 且
E’?E,则称 图 G’ 是 图 G 的 子图 。
子 图：
边较少的图。通常边数 <<n2
边很多的图。无向图中，边数接近 n(n-1)/2；
有向图中，边数接近 n(n-1)
12
带权图,即边上带权的图。其中 权 是指每条边可以标上具有某种含义的数值（即与边相关的数）。
连通图,在 无向图 中,若从顶点 v1到顶点 v2有路径,则称顶点 v1
与 v2是连通的。如果图中任意一对顶点都是连通的,
则称此图是 连通图 。
非连通图的极大连通子图叫做 连通分量 。
＝ 带权图在有向图中,若对于每一对顶点 vi和 vj,都存在一条从
vi到 vj和 从 vj到 vi的路径,则称此图是 强连通图 。
非强连通图的极大强连通子图 叫做 强连通分量 。
强连通图：
网 络：
有两类图形不在本课程讨论之列：
13
邻接点：
有向边 (u,v)称为弧，边的始点 u叫 弧尾,终点 v叫 弧头顶点 v的度 是与它相关联的边的条数。记作 D(v)。
在 有向图 中,顶点的度等于该顶点的 入度 与 出度 之和。
顶点 v 的入度 是以 v 为终点的有向边的条数,记作 ID(v);
顶点 v 的出度 是以 v 为始点的有向边的条数,记作 OD(v)。
若 (u,v) 是 E(G) 中的一条边，则称 u 与 v 互为 邻接顶点弧头和弧尾：
度、入度和出度：
生成树,是一个 极小连通子图,它含有图中全部顶点,但只有 n-1条边 。
如果在生成树上添加 1条边，必定构成一个环。
若图中有 n个顶点，却少于 n-1条边，必为非连通图。
生成森林：
问,当有向图中仅 1个顶点的入度为 0,其余顶点的入度均为 1，此时是何形状？
由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。
答,是树！而且是一棵有向树！
14
简单路径,路径上各顶点 v1,v2,...,vm 均 不互相重复 。
回 路：
例：
若路径上第一个顶点 v1 与最后一个顶点 vm 重合，则称这样的路径为 回路 或 环 。
路径,在图 G＝ (V,E) 中,若从顶点 vi 出发,沿一些边经过一些顶点 vp1,vp2,…,vpm，到达顶点 vj。则称顶点序列 ( vi vp1
vp2,.,vpm vj ) 为从顶点 vi 到顶点 vj 的 路径 。它经过的边 (vi,
vp1),(vp1,vp2),...,(vpm,vj)应当是属于 E的 边 。
路径长度,非带权图的路径长度是指此路径上边的 条数 ；带权图的路径长度是指路径上各边的 权 之和 。
15
例 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
16
例
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
17
连通图例
2 4 5
1 3 6
强连通图
3
5
6
例非连通图连通分量例
2 4 5
1 3 6
18
CreatGraph(&G,V,VR),//按定义 (V,VR) 构造图
DestroyGraph(&G),//销毁图
LocateVex(G,u); //若 G中存在顶点 u,则返回该顶点在图中位置；否则返回其它信息。
GetVex(G,v); //返回 v 的值。
PutVex(&G,v,value); //对 v赋值 value。
FirstAdjVex(G,v); //返回 v的第一个邻接点 。若该顶点在 G 中没有邻接点,则返回“空”。
NextAdjVex(G,v,w); //返回 v的 (相对于 w的 )下一个邻接点。若是最后一个则返回“空”。
InsertVex(&G,v); //在图 G中增添新顶点 v。
DeleteVex(&G,v); //删除 G中顶点 v及其相关的弧。
InsertArc(&G,v,w); //在 G中增添弧 <v,w>，若 G是无向的,则还增添对称弧 <w,v>。
DeleteArc(&G,v,w); //在 G中删除弧 <v,w>，若 G是无向的,则还删除对称弧 <w,v>。
DFSTraverse(G,v,Visit()); //从顶点 v起深度优先遍历图 G,并对每个顶点调用 Visit一次。
BFSTraverse(G,v,Visit()); //从顶点 v起广度优先遍历图 G,并对每个顶点调用 Visit一次。
结构的建立和销毁
对顶点的访问操作
插入或删除顶点
插入和删除
对邻接点的操作
遍历基本操作
19
7.2 图的存储结构图的特点：非线性结构（ m,n ）
邻接表
邻接多重表
十字链表设计为邻接矩阵链式存储结构：
顺序存储结构,无！ （多个顶点，无序可言）
但可 用 数组 描述元素间关系。
可用多重链表重点介绍,邻接矩阵 (数组 )表示法邻接表 (链式 )表示法
20
一、邻接矩阵 (数组 )表示法
建立一个 顶点表 （记录各个顶点信息） 和一个 邻接矩阵 （表示各个顶点之间关系）。
设图 A = (V,E) 有 n 个顶点，则图的邻接矩阵是一个二维数组
A.Edge[n][n]，定义为：
v1 v2
v3
v5v4
A
例：
邻接矩阵：
A.Edge =
（ v1 v2 v3 v4 v5 ）
v1
v2
v3
v4
v5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
分析 1,无向图的邻接矩阵是 对称 的；
分析 2,顶点 i的 度 ＝第 i 行 (列 ) 中 1 的个数 ；
特别,完全图 的邻接矩阵中，对角元素为 0，其余全 1。
1 1
1 1 1
1 1 1
1 1 1
1 1 1
0
1
1
顶点表：
=
,
),(,,]][[.
否则或者如果
0
><1A EjiEjijiEdge
21
例,有向图的邻接矩阵分析 1,有向图的邻接矩阵 可能是不对称 的。
分析 2,顶点的 出度 =第 i行元素之和,OD( Vi )=?A.Edge[ i ][j ]
顶点的 入度 =第 i列元素之和。 ID( Vi )=? A.Edge[ j ][i ]
顶点的 度 =第 i行元素之和 +第 i列元素之和,
即,TD(Vi)=OD( Vi ) + ID( Vi )
v1 v2
v3 v4
A 邻接矩阵,A.Edge =
( v1 v2 v3 v4 )
v1
v2
v3
v4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
注,在有向图的邻接矩阵中，
第 i行含义：以结点 vi为尾的弧 (即出度边）；
第 i列含义：以结点 vi为头的弧 (即入度边）。
顶点表：
1 1
1
1
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
22
容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
n个顶点需要 n*n个单元存储边 (弧 );空间效率为 O(n2)。 对稀疏图而言尤其浪费空间。
特别讨论,网（即有权图）的邻接矩阵定义为,A.Edge[ i ][ j ]= Wij <vi,vj> 或（ vi,vj） ∈ VR∞ 无边（弧）
v1 v2
v3
v4
N
v5
v6
5
48
9
7
5
5
61
3
以有向网为例：
邻接矩阵,∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
N.Edge =
( v1 v2 v3 v4 v5 v6 )
邻接矩阵法 优点：
邻接矩阵法 缺点：
顶点表：
5 7
4
8 9
5 6
5
3 1
∞ 5 ∞ 7 ∞ ∞
∞∞ 4 ∞ ∞ ∞
8 ∞ ∞ 9
∞∞ 5 ∞ ∞ 6
∞∞ 5 ∞ ∞
3 ∞ 1 ∞
23
注,用两个数组分别存储顶点表和邻接矩阵
#define INFINITY INT_MAX //最大值 ∞
#define MAX_VERTEX_NUM 20 //假设的最大顶点数
Typedef enum {DG,DN,AG,AN } GraphKind; //有向 /无向图，有向 /无向网
Typedef struct ArcCell{ //弧（边）结点的定义
VRType adj; //顶点间关系，无权图取 1或 0；有权图取权值类型
InfoType *info; //该弧相关信息的指针
} ArcCell,AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ];
Typedef struct{ //图的定义
VertexType vexs [MAX_VERTEX_NUM ] ; //顶点表，用一维向量即可
AdjMatrix arcs; //邻接矩阵
int vernum,arcnum; //顶点总数，弧（边）总数
GraphKind kind; //图的种类标志
} Mgraph;
图的邻接矩阵存储表示对于 n个顶点的图或网，空间效率 =O(n2)
24
Status CreateUDN(Mgraph &G) { //无向网的构造，用邻接矩阵表示
scanf(&G.vexnum,&G.arcnum,&IncInfo); //输入总顶点数，总弧数和信息
for(i=0;i<G.vexnum,;++i) scanf(&G.vexs[i] );//输入顶点值，存入一维向量中
for (i=0; i<G.vexnum; ++i) //对邻接矩阵 n*n个单元初始化,adj=∞,info=NULL
for(j=0;j<G.vexnum;++j) G.arcs[i][j]={INFINITY,NULL};
for (k=0;k<G.arcnum;++k){ //给邻接矩阵有关单元赋初值 (循环次数＝弧数
scanf(&v1,&v2,&w); //输入弧的两顶点以及对应权值
i=LocateVex(G,v1); j=LocateVex(G,v2); //找到两顶点在矩阵中的位臵 (n次?
G.arcs[i][j].adj=w; //输入对应权值
if(IncInfo) Input(*G.arcs[i][j].info); //如果弧有信息则填入
G.arcs[i][j] = G.arcs [j] [i]； //无向网是对称矩阵
}
return OK;
} //CreateUDN
例：用邻接矩阵 生成无向网 的算法对于 n个顶点 e条弧的网，
建网时间效率 = O(n2+n+e*n)
25
二、邻接表 (链式 )表示法
对每个顶点 vi 建立一个 单链表,把与 vi有关联的 边的信息 （即度或出度边） 链接 起来，表中每个结点都设为 3个域；
每个单链表还应当附设一个 头结点 （设为 2个域），存 vi信息；
adjvex nextarc infodata firstarc
表结点头结点邻接点域,表示 vi一个邻接点的 位臵链域,指向
vi下一个边或弧的结点数据域,与边有关信息
（如权值）
数据域,存储顶点 vi 信息链域,指向单链表的第一个结点
每个单链表的 头结点另外用顺序存储结构 存储。
26
例：无向图的邻接表
v1 v2
v3
v5v4
邻接表
0
1
2
3
4
^13
34 ^1
4 2 ^0
例：有向图的邻接表
v1 v2
v3 v4
V4
V3
^V2
V1 2
^3
^0
^1
邻接表 (出边 )
注,邻接表不唯一，因各个边结点的链入顺序是任意的。
v1
v2
v3
v4
v5 23 ^1
4 2 ^0
当邻接表的存储结构形成后，
图便唯一确定！
27
分析 1,对于 n个顶点 e条边的无向图,邻接表中除了 n个头结点外，只有 2e个表结点,空间效率为 O(n+2e)。
若是稀疏图 (e<<n2)，则比邻接矩阵表示法 O(n2)省空间。
邻接表存储法的特点：
分析 2,在 有向图 中,邻接表中除了 n个头结点外,只有 e个表结点,
空间效率为 O(n+e)。 若是稀疏图，则比邻接矩阵表示法合适。
—它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？
邻接表的 缺点：
怎样计算有向图顶点的出度？
怎样计算有向图顶点的入度？
怎样计算有向图顶点 Vi的度,需遍历全表邻接表的 优点：
TD( Vi )=单链表中链接的结点个数
OD( Vi )＝ 单链出边表中链接的结点数
I D( Vi ) ＝ 邻接点为 Vi的弧个数
TD( Vi ) = OD( Vi ) + I D( Vi )
空间效率高； 容易寻找顶点的邻接点；
判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
28
讨论：邻接表与邻接矩阵有什么异同之处？
联系,邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数 。
区别：
① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但 邻接表不唯一 （链接次序与顶点编号无关）。
② 邻接矩阵的空间复杂度为 O(n2),而邻接表的空间复杂度为 O(n+e)。
用途,邻接矩阵多用于稠密图的存储 (e接近 n(n-1)/2)；而邻接表多用于稀疏图的存储 (e<<n2)
29
图的邻接表存储表示
#define MAX_VERTEX_NUM 20 //假设的最大顶点数
Typedef struct ArcNode {
int adjvex; //该弧所指向的顶点位臵
struct ArcNode *nextarcs; //指向下一条弧的指针
InfoArc *info; //该弧相关信息的指针
} ArcNode；
Typedef struct VNode{ //顶点结构
VertexType data; //顶点信息
ArcNode * firstarc; //指向依附该顶点的第一条弧的指针
} VNode,AdjList[ MAX_VERTEX_NUM ];
Typedef struct { //图结构
AdjList vertics ; //应包含邻接表
int vexnum,arcnum; //应包含顶点总数和弧总数
int kind; //还应说明图的种类（用标志）
} ALGraph; //图结构空间效率为 O(n+2e)或 O(n+e)
时间效率为 O(n+e*n)
30
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
31
一、深度优先搜索二、广度优先搜索
7.3 图的遍历遍历定义,从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做 图的遍历,它是 图的 基本运算。
遍历实质,找每个顶点的邻接点的过程。
图的特点,图中可能存在 回路,且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点 。
解决思路,可设臵一个 辅助数组 visited [n ]，用来标记每个被访问过的顶点。它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i被访问，就立即改 visited [i]为 1，防止它被多次访问。
图常用的遍历：
怎样避免重复访问？
32
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
V4 V5 V6 V7
V8
深度优先搜索 (DFS)
V1 V2 V4 V8 V5 V3 V6 V7
生成树遍历序列广度优先搜索 (BFS)
V1V2V3V4V5V6V7V8
最短路径！
图的遍历 -例子
33
一、深度优先搜索 ( DFS )
基本思想,——仿树的先序遍历过程 。
Depth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
DFS 结果例 1：
→ → → →
→ → →
v2 v4 v8
v5 v3 v6 v7
例 2：
v2 → v1 → v3 → v5 →
DFS 结果
v4 → v6
起点起点遍历步骤
1、深度优先搜索,
有向图的实例,为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。
如：结点 5的邻接结点有两个 6,7，则先访问结点 6，再访问结点 7。
5
6
7
2
4
1
3
5
6 7
2
3
1
4
·
·
·
· ·
·
·
从结点 出发的搜索序列：
5,6,2,3,1,4,7
适用的数据结构：栈
5
1
2
43
·
·
· ·
从结点 出发的搜索序列：
1,2,3,4没有搜索到所有的结点，必须另选图中未访问过的结点，
继续进行搜索。
1
35
一、深度优先搜索遍历图连通图的深度优先搜索遍历,从图中某个顶点 V0 出发，访问此顶点，然后依次从 V0的 各个未被访问的 邻接点出发深度优先搜索遍历图,直至图中所有和 V0有路径相通的顶点都被访问到。
SG1 SG2 SG3
W1,W2和 W3均为 V 的邻接点,SG1,SG2 和 SG3 分别为含顶点 W1,W2和 W3
的子图。
访问顶点 V ;
for (W1,W2,W3 )
若 该邻接点 W未被访问,
则 从它出发进行深度优先搜索遍历。
V
w1 w3w2
1,从深度优先搜索遍历连通图的过程类似于树的先根遍历 ;
解决的办法是,为每个顶点设立一个,访问标志 visited[w]”;
2,如何判别 V的邻接点是否被访问？
36
深度优先搜索（遍历）步骤：
详细归纳：
在访问图中某一起始顶点 v后,由 v出发,访问它的任一邻接顶点 w1；
再从 w1出发,访问与 w1邻接但还未被访问过的顶点 w2；
然后再从 w2出发,进行类似的访问,…
如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。
如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问；
如果没有,就 再退回一步 进行搜索。
重复上述过程,直到连通图中所有顶点都被访问过为止。
简单归纳：
访问起始点 v;
若 v的第 1个邻接点没访问过，深度遍历此邻接点；
若当前邻接点已访问过，再找 v的第 2个邻接点重新遍历。
37
讨论 1：计算机如何实现 DFS？
1 2 3 4 5 6
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 0 0 0
6 0 0 0 0 0 0
0
0
0
0
0
0
1
2
3
4
5
6
0
1
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
DFS 结果邻接矩阵
A
辅助数组 visited [n ]
起点
v2→v1→v3→v5→ v4→v6
——开辅助数组 visited [n ]！
例：
1 1 1
1 1
1 1
1 1
1 1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
38
讨论 2,DFS算法如何编程？
DFS1(A,n,v) {
visit（ v） ;
visited[v]=1;
for( j=1; j<=n; j++)
if ( A[v,j] && ! visited[j] ) DFS1(A,n,j);
return;
}
——可以用递归算法！
//A[n][n]为邻接矩阵,v为起始顶点 (编号）
//访问（例如打印）顶点 v
A[v,j] ＝ 1
有邻接点
visited [n ]=0
未访问过
//访问后立即修改辅助数组标志
//从 v所在行从头搜索邻接点建议,在递归函数中增加一计数器 sum，初值为 n，每访问一次就减 1,减到 0则 return，可避免递归时间过长。
39
讨论 3：在图的邻接表中如何进行 DFS？
v0 → v1 → v2 → v3
DFS 结果
0
0
0
0
0
1
2
3
辅助数组 visited [n ]
例：
—照样借用 visited [n ]！
起点
0
1
2
3
注意,在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。
1
0
0
0
1
1
0
0
1
1
1
0
1
1
1
1
40
讨论 4：邻接表的 DFS算法如何编程？
DFS2(List,v,p) {
visit（ v） ;
visited[v]=1;
p=p->link;
if (!p) return;
v=p->data;
while ( !visited[v] ) DFS2(list,v,p);
return;
}
//List为邻接表,v为起始顶点 (编号），
//p为 v所在那条单链表的的头指针。
//访问后立即修改辅助数组标志
//若指针为空，则结束本次遍历
//指向 v的链表中下一邻接点
//取出链表中当前邻接点
——仍可用递归算法
41
void DFSTraverse(Graph G,Status (*Visit)(int v)) {
// 对图 G 作深度优先遍历。
VisitFunc = Visit;
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) DFS(G,v);
//对尚未访问的顶点调用 DFS
}
首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。
非连通图的深度优先搜索遍历
42
void DFS(Graph G,int v) {
// 从顶点 v出发,深度优先搜索遍历连通图 G
visited[v] = TRUE; VisitFunc(v);
for (w=FirstAdjVex(G,v);
w!=0; w=NextAdjVex(G,v,w))
if (!visited[w]) DFS(G,w);
//对 v的尚未访问的邻接顶点 w递归调用 DFS
} // DFS
时间复杂性：
邻接矩阵,O(n2)
邻接表,O(n+e)
n：结点数
e,边数结论：
稠密图 适于在邻接矩阵上进行深度遍历；
稀疏图 适于在邻接表上进行深度遍历。
43
a b
c
h
d e
k
f
g
8
1
2 3 4 5
6
7
0
F F F F F F F F F
0 1 2 3 4 5 6 7 8
T T T T T T T T T
a c h d k f e b g
访问标志,
访问次序,
例如,a
c
h
d k
f e
44
二、广度优先搜索 ( BFS )
基本思想,——仿树的层次遍历过程 。
Breadth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
BFS 结果,例：
→ →
→
→v2 v3
→v4 v5 →v6 v7→ v8
例：
v3 →
BFS 结果,
v4 → v5 →
起点遍历步骤起点
v2 → v1 → v6 →
v9 → v8 → v7
无向图的实例,为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。
结点 1的邻接结点有三个 2,12,11，则先访问结点 2,11，再访问结点 12。
广度 (宽度 )优先搜索,
图的广度优先的访问次序：
1,2,11,12,3,6,7,10,4,5,8,9
适用的数据结构：队列
1
2 12 11
3 6 7 10
4 5 8 9
1
2 1211
3 6 7 10
4 5 8 9
·
·
·
·
·
·
· ·
· ·
· ·
队列的变化：
广度（宽度）优先搜索,
A
B C D
E F G H I J K
L
树的按层次进行访问的次序：
A,B,C,D,E,F,G,H、
I,J,K,L
适用的数据结构：队列
A
B C D
1、结点 A进队
2、结点 A出队、访问，队空
3、结点 A的儿子结点进队
4,结点 B出队、访问
5、结点 B的儿子结点进队
6、结点 C出队、访问
7、结点 C的儿子结点进队
C D
E F GC D
E F GD
E F GD H
47
广度优先搜索（遍历）步骤简单归纳：
在访问了起始点 v之后，依次访问 v的邻接点；
然后再依次访问这些顶点中未被访问过的邻接点；
直到所有顶点都被访问过为止。
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。
48
讨论 1：计算机如何实现 BFS？
邻接表
——除辅助数组 visited [n ]外，
还需再开一辅助队列！例：
起点辅助队列
v2已访问过了
BFS 遍历结果入队！
初始 f=n-1,r=0
49
讨论 2,BFS算法如何编程？
BFS1(List,n,v) {
Visit(v); Visited[v]=1;
front=n-1; rear=0; q[rear]=v;
while(rear!=front) {
front=(front+1)%n; v=q[front];
p=List[v].firstarc;
while ( !p ) {
if(! Visited[adjvex(p)] ) {
Visit(adjvex(p)); Visited[adjvex(p)]=1;
rear=(rear+1)%n; q[rear]= adjvex(p)}
p=nextarc(p);
}
}
return
}
——层次遍历应当用队列！
//List为邻接表,v为起点,Q[n]为辅助队列
//访问（例如打印）顶点 v并修改标志
//指向单链表中下一个邻接点
//队列指针初始化
//起始点入队
//队不空时
//访问过的顶点出队
//P指向第 1个邻接点
//未到表尾，且邻接域未访问过，
//则先输出再改标
//记，最后再入队图的广度遍历程序使用的变量说明,Boolean visited[MAX];//用于标识结点是否已被访问过
Status (*VisitFunc)(int v); //函数变量
void BFSTraverse( Graph G,Status ( * VisitFunc) (int v));
{ VisitFunc = Visit;
for (v=0;v<G.vexnum;++v) visited[v]=FALSE;
InitQueue(Q);
for (v=0; v<G.vexnum; ++v)
if (!Visited[v]) {
Visited[ v ] = TRUE; Visit(v); EnQueue(Q,v);
while (!EmptyQueue(Q)) {
DeQueue(Q,u);
for (w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if (!Visited[w]) {
Visited[v] =TRUE; Visit(v); EnQueue(Q,w)
} ;
}
}
}
时间复杂性：
邻接矩阵,O(n2)
邻接表,O(n+e)
n：结点数
e,边数
51
BFS 算法效率分析,
DFS与 BFS之比较：
空间复杂度相同，都是 O(n)(借用了堆栈或队列）；
时间复杂度只与存储结构（ 邻接矩阵或邻接表 ）有关，
而与搜索路径无关。
如果使用邻接表来表示图，则 BFS循环的总时间代价为
d0 + d1 + … + d n-1 = O(e),其中的 di 是顶点 i 的度 。
如果使用邻接矩阵，则 BFS对于每一个被访问到的顶点，
都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为 O(n2)。
（设图中有 n 个顶点,e 条边）
52
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdatafirstarc
5
5
4 3 ^
^
^
adjvexnext
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
图的广度遍历演示
53
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdatafirstarc
5
5
4 3 ^
^
^
adjvexnext
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
54
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
vexdatafirstarc
5
5
4 3 ^
^
^
adjvexnext
5 5
1 ^5
1
1
4 3 ^
2
2
55
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0 1 2 3 4 5 6 7
迷宫及其最短历经求迷宫的最短路径迷宫简介迷宫可用一个二维位数组表示,0表示连通,1表示不连通。连通方向又分为 4连通和八连通两种。
如下图所示，右图表示了一个八连通的所有方向所形成的有向图。
...
.,
.,,,,.
...,
..,,...
.,
表示迷宫的方向图最后形成有向图
56
g = i+di[v]
h = j+di[v]
v = 0,1,2,3,4,5,6,7
（ 1）如何得到和迷宫相应的有向图求迷宫的最短路径
di 0 1 1 1 0 -1 -1 -1
dj 1 1 0 -1 -1 -1 0 1
下标增量数组
i-1,j-1 i+1,j-1 i-1,j+1
i,j+1
i+1,j+1
i,j
i+1,ji+1,j-1
i,j-1
8个相邻位置的坐标
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0 1 2 3 4 5 6 7
迷宫及其最短历经
...
.,
.,,,,.
...,
..,,...
.,
表示迷宫的方向图
57
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0 1 2 3 4 5 6 7
（ 2）如何得到路径求迷宫的最短路径
0,0^ 0,0 0,0 0,0 0,0 0,0 0,0 ^
最短路径搜索过程中的路径
Q.front
Q.rear
0 2 6 6 6
5 721
2
5 6 7 7 7
4 4 5 6
653 4
3 4
最短路径的搜索过程
...
.,
.,,,,.
...,
..,,...
.,
表示迷宫的方向图
58
数据结构：
求迷宫的最短路径程序：
链式队列：纪录搜索过程堆栈：保存结果求 m行 n列的迷宫 maze中从入口 [0][0]到出口 [m-1][n-1]的最短路径，若存在，
则返回 TRUE，此时栈 S中从栈顶到栈底为最短路径所经过的各个方位 ;若该迷宫不通，则返回 FALSE，此时栈 S为空栈。
该路口可行条件：
若 0<=npos,xpos<m-1,
0<=npos,ypos<n-1,
Maze[npos.xpos][npos.ypos]==0,
visited[npos.xpos][npos.ypos]==FALSE
则 Pass函数为 TRUE,否则为 FALSE
堆栈操作程序最短路径程序迷宫搜索程序队列处理程序堆栈数组：表示迷宫、已到位置和方向
59
ypedef struct { int xpos; int ypos; } PosType;
typedef struct DQNode {
PosType seat;
struct DQNode *next;
DQNode *pre;
} DQNode,*DQuencePtr;
typedef struct { DQuencePtr fronr; DQuencePtr rear; } DLinkQuence;
void InitQuence( DLinkQuence &Q ) { Q,front = NULL; Q.rear = NULL; }
void EnQuence( DLinkQuence &Q,PosType e ) {
p = new DQNode;
p->seat.xpos = e.xpos;
p->seat.ypos = e.ypos;
p->next = NULL;
if (!Q.rear) { p->pre = NULL; Q.rear = p; Q.front = p; }
else { p->pre = Q->front; Q.rear-?next = p; Q.rear = p; }
}
void GetHead( DLinkQuence Q,PosType &e ) {
e.ypos = Q.front->seat.ypos; e.xpos = Q.front->seat.xpos;
}
void DeQuence( DLinkQuence &Q ) { Q.front = Q.Front->next; }
void QuenceEmpty( DLinkQuence Q ) { return (Q.front == NULL); }
60
bool ShortestPath(int maze[][],int m,int n,Stack &S)
{ DLinkQueue Q;
bool visited[m][n];
InitQueue(Q); // 队列初始化
for(i=0; i<m; i++) // 对访问标志数组置初值
for(j=0; j<n; j++) visited[i][j] = FALSE;
if (maze[0][0]!=0) return FALSE;
e.xpos = 0; e.ypos = 0; EnQueue(Q,e); found = FALSE;
while(!found && !QueueEmpty(Q)) {
GetHead(Q,curpos); // 取当前的队头顶点 curpos
for (v=0; v<8,!found; v++) { // 搜索 8个方向的邻接点
npos = NextPos(curpos,v); // 类型为 PosType的 npos是搜索到的下一点
if (Pass(npos)) { // 如果下一点可走通则入队列
EnQueue(Q,npos); visited[npos.xpos][npos.ypos] = TRUE;
}//if
if (npos.xpos=n-1 && npos.ypos=m-1) found=TRUE; // 找到出口
}//for
DeQueue(Q); // 出队列，准备从下一邻接点搜索
}//while
if (found) {
InitStack(S); p = Q.rear; // 从出口顶点以 pre指针为导向，反向查看
while(!p) { Push(S,p->seat); p=p->pre; } //while
return TRUE;
}//if
else return FALSE;
}//ShortestPath
时间复杂度,O(m*n)
int Pass( PosType npos )
{
if ( npos,xpos>=0 && npos.xops<m-1 &&
npos,ypos>=0 && npos.ypos<n-1 &&
Maze[npos.xpos][npos.ypos]==0 &&
visited[npos.xpos][npos.ypos]==FALSE ) return TRUE;
else return FALSE;
}
61
生成树,是一个极小连通子图，它含有图中全部顶点，但只有
n-1条边。
生成森林,由若干棵 生成树 组成，含全部顶点，但构成这些树的边是最少的。
思考 1：对连通图进行遍历，得到的是什么？
—得到的将是一个极小连通子图，即图的 生成树 ！
由深度优先搜索得到的生成树，称为深度优先搜索生成树。
由广度优先搜索得到的生成树，称为广度优先搜索生成树。
思考 2：对非连通图进行遍历，得到的是什么？
— 得到的将是各连通分量的生成树，即图的 生成森林 ！
7.4 连通图的小生成树求图的生成树生成树的特征 —n个顶点的 连通 网络的生成树有 n个顶点,n-1条边。
求生成树的方法 —DFS(深度优先搜索 )和 BFS(广度优先搜索 )
62
欲在 n个城市间建立通信网，则 n个城市应铺 n-1条线路；但因为每条线路都会有对应的经济成本，而 n个城市可能有 n(n-1)/2条线路，那么,如何选择 n–1条线路，使总费用最少？
典型用途：
数学模型：
顶点 ———表示城市，有 n个；
边 ————表示线路，有 n–1条；
边的权值 —表示线路的经济代价；
连通网 ——表示 n个城市间通信网。
显然此连通网是一个生成树！
问题抽象,n个顶点的生成树很多，需要从中选一棵 代价最小 的生成树，即该树 各边的代价之和 最小 。 此树便称为最小生成树
MST(Minimum cost Spanning Tree)
63
例：画出下图的生成树
DFS
生成树
v0 v1
v2
v4v4v3
邻接表
0
1
2
3
4
^13
34 ^1
4 2 ^0
v4
v3
v2
v1
v0
23 ^1
4 2 ^0
v0
v2
v1
v4
v3 BFS
生成树
v0
v1v3
v2v4
无向连通图
64
有多种算法，但最常用的是以下两种：
最小生成树的 MST 性质如下：
Kruskal（克鲁斯卡尔）算法
Prim（普里姆）算法
Kruskal算法特点,将边归并,适于求 稀疏网 的最小生成树。
Prime算法特点,将顶点归并,与边数无关，适于 稠密网。
这两个算法，都是利用 MST 性质来构造最小生成树的。
若 U集是 V的一个非空子集，若 (u0,v0)是一条 最小权值的边,其中
u0?U,v0?V-U；则,(u0,v0)必在最小生成树上 。
应用,n个城市建网，如何选择 n–1条线路，使总费用最少？
求最小生成树目标,在网的多个生成树中，寻找一个 各边权值之和最小 的生成树。
65
步骤,
(1) 首 先构造一个只有 n个顶点但没有边的非连通图 T={V,?},
图中每个顶点自成一个连通分量。
(2) 当在边集 E 中选到一条具有最小权值的边时,若该边的两个顶点落在 T中不同的连通分量上，则将此边加入到生成树的边集合 T 中；否则将此边舍去，重新选择一条权值最小的边。
(3) 如此重复下去，直到所有顶点在同一个连通分量上为止。
此时的 T即为所求（ 最小生成树 ）。
一、克鲁斯卡尔 (Kruskal)算法设 N ={V,E }是有 n个顶点的连通网，
Kruskal算法采用 邻接表 作为图的存储表示
66
例：应用克鲁斯卡尔算法构造最小生成树的过程
√
√
√ √
×
√
×
√
67
Kruskal（克鲁斯卡尔）算法例,1
4
65
2 3
1
56
55
463
6
2
15
43 2
1
3
5
2 4
6
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
12
7
8
例如,
68
计算机内怎样实现 Kruskal算法？
设计思路：
① 设每条边对应的结构类型为：
特点,将 边 归并 ——适于求 稀疏网 的最小生成树。
故采用 邻接表 作为图的存储表示 。
Lchild vi vj weight Rchild
② 取堆顶元素，加入到对应最小生成树的新邻接表中（初始为空），从堆中删除它并重新排序堆，每次耗时 log2(e)；
③ 重复上一步，注意每次加入时要判断是否,多余,（即是否已被新表中的连通分量包含）；
④ 直到堆空。
显然,Kruskal算法的时间效率＝ O(elog2e)
初态,按权值排序 (以 堆排序 为佳，堆顶即为权值最小的边）
69
算法描述,
构造非连通图 ST=( V,{ } );
k = i = 0; // k 计选中的边数
while (k<n-1) {
++i;
检查边集 E 中第 i 条权值最小的边 (u,v);
若 (u,v)加入 ST后不使 ST中产生回路，则输出边 (u,v); 且 k++;
}
最小代价生成树
1
2 43
5 6
6 1
6
5
5 5
63 4 2
1
2 43
5 6
1
5
3 4 2
5
5
最小代价生成树（简称：最小生成树）
实例的执行过程
1
2 43
5 6
6 1
6
5
5 5
63 4 2
图 G
1、初始连通分量,{1},{2},{3},{4},{5},{6}
2、反复执行添加、放弃动作。 条件：边数不等于 n-1时边 动作 连通分量
(1,3) 添加 {1,3},{4},{5},{6},{2}
(4,6) 添加 {1,3},{4,6},{2},{5}
(2,5) 添加 {1,3},{4,6},{2,5}
(3,6) 添加 {1,3,4,6},{2,5}
(1,4) 放弃 因构成回路
(3,4) 放弃 因构成回路
(2,3) 添加 {1,3,4,5,6,2}
最小代价生成树
1
2 43
5 6
1
5
3 4 2
5
5
算法实现要点,每个结点增加一个数据场，用于标识该结点所属的集合。可用于判断新的边加入后是否构成回路。
71
（ 0）用顶点数组和边数组存放顶点和边信息
（ 1）初始时，令每个顶点的 set互不相同；每个边的 flag为 0
（ 2）选出权值最小且 flag为 0的边
（ 3）若该边依附的两个顶点的 set 值不同，即非连通，则令该边的 flag=1,选中该边；再令该边依附的两顶点的集合以及两集合中所有顶点的 set相同若该边依附的两个顶点的 set值相同，即连通，则令该边的 flag=2,即舍去该边
（ 4）重复上述步骤，直到选出 n-1条边为止顶点结点：
typedef struct
{ int data; //顶点信息
int set;
} VEX;
边结点：
typedef struct
{ int vexs,vexe; //边依附的两顶点
int score; //边的权值
int flag; //标志域
} EDGE;
72
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
data set
1
2
4
5
3
6
1
2
4
5
3
6
1
2
4
5
3
6
vexs score
1
1
2
2
1
3
2
3
3
5
4
4
vexe 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
73
取图中任意一个顶点 v作为生成树的根,之后往生成树上添加新的顶点 w。 在添加的顶点 w和已经在生成树上的顶点 v之间必定存在一条边,并且该边的权值在所有连通顶点 v和 w之间的边中取值最小。
之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。
二、普里姆 (Prim)算法一般情况下所添加的顶点应满足下列条件,在生成树的构造过程中，图中 n 个顶点分属两个集合,已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集 V-U，则应在所有连通 U中顶点和 V-U
中顶点的边中选取权值最小的边。
U
V-U
74
（ 1）初始状态,U ={u0 },（ u0∈ V）,TE={ },
（ 2）从 E中选择顶点分别属于 U,V-U两个集合、且权值最小的边 （ u0,v0),将顶点 v0归并到集合 U中，边 （ u0,v0)
归并到 TE中；
（ 3）直到 U=V为止。此时 TE中必有 n-1条边,T＝ (V,{TE})
就是最小生成树。
设,N =（ V,E）是个连通网，
另设 U为最小生成树的顶点集,TE为最小生成树的边集。
构造步骤,
普利姆 (Prim)算法
75
例 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
76
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
12
7
例如,
所得生成树权值和 =14+8+3+5+16+21 = 67
例,1
4
65
2 3
1
56
55
463
6
2
3
6
42
5
1
[注 ],在最小生成树的生成过程中，所选的边都是一端在
V-U中，另一端在 U中。
77
设计思路：
① 增设一辅助数组 Closedge[n],每个 数组分量都 有两个域：
要求,使 Colsedge[i].lowcost = min((u,vi)) u?U
计算机内怎样实现 Prim（普里姆）算法？
Prime算法特点,将顶点归并,与边数无关，适于稠密网。
故采用 邻接矩阵 作为图的存储表示。
adjvex lowcost
vi在 U中的邻点 u
Colsedge[i]
V-U中顶点 vi u与 vi之间对应的边权从 u1~un中挑
78
vex
lowcost
vex
lowcost
vex
lowcost
vex
lowcost
vex
lowcost
vex
lowcost
V-UU65432vclosedge
1
42 3
5 6
16 5
5 5
3 6 4 2
6
具体示例：
{1} {2,3,4,5,6}
1
6
1
1
1
5
1
∞
1
∞
{1,3} {2,4,5,6}035 15
3
6
3
4
{1,3,6} {2,4,5}35 0 62 36 0
{1,3,
6,4} {2,5}
3
5 0
3
60 0
{1,3,6,
4,2} {5}0 0 0 0
2
3
0 0 0 0 0
{1,3,6,
4,2,5} {}
起点
5
3
1
2
3
4
5
6
显然,Prim算法的时间效率＝ O(n2)
79
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
12
7
closedge
0 1 2 3 4 5 6
Adjvex
Lowcost
a a a
19 14 18
例如,
e
12
e e
8 16
d
3
d d
7 21
c
5
19 m m 14 m 18
19 5 7 12 m m
m 5 3 m m m
m 7 3 8 21 m
14 12 m 8 m 16
m m m 21 m 27
18 m m m 16 27
80
普里姆算法 克鲁斯卡尔算法时间复杂度 O(n2) O(eloge)
稠密图 稀疏图算法名适应范围比较两种算法
81
7.5 求最短路径两种常见的最短路径问题：
一,单源最短路径 —用 Dijkstra（迪杰斯特拉） 算法二、所有顶点间的最短路径 —用 Floyd（弗洛伊德）算法典型用途,交通问题。如：城市 A到城市 B有多条线路，但每条线路的交通费（或所需时间）不同，那么,如何选择一条线路，使总费用（或总时间）最少？
问题抽象,在 带权有向图 中 A点（源点）到达 B点（终点）的多条路径中，寻找一条 各边权值之和最小 的路径，即最短路径。
（注：最短路径与最小生成树不同，路径上不一定包含 n个顶点）
任意两顶点之间一顶点到其余各顶点
82
一、最短路径用带权的有向图表示一个交通运输网，图中：
顶点 ——表示城市边 ——表示城市间的交通联系权 ——表示此线路的长度或沿此线路运输所花的时间或费用等问题,从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 ——最短路径
– 从某个源点到其余各顶点的最短路径
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
83
二、单源最短路径 (Dijkstra算法 )
目的,设一有向图 G=(V,E)，已知各边的权值，以某指定点 v0
为源点，求从 v0到图的其余各点的最短路径。 限定各边上的权值大于或等于 0。
例 1：
源点从 F→A 的路径有 4条：
① F→A,24
② F→B→A,5＋ 18=23
③ F→B→C→A,5+7+9=21
④ F→D→C→A,25+12+9=36
又：
从 F→B 的最短路径是哪条？
从 F→C 的最短路径是哪条？
84
v0 (v0,v1) 10
源点 终点 最 短 路 径 路径长度
(v0,v1,v2) (v0,v3,v2)
(v0,v 3) 30
v1
v2
v3
v4 100(v0,v4) (v0,v3,v4)(v
0,v3,v2,v4)
例：
60
0
1
2
3
4
50
90 70
讨论：计算机如何自动求出这些最短路径？
(v0,v1,v2,v4) 60
85
求 从源点到其余各点的最短路径 的算法的基本思想,
依 最短路径的长度 递增的次序求得各条路径源点
v1
…
其中,从源点到顶点 v的最短路径 是所有最短路径中长度最短者。
v2
求最短路径的迪杰斯特拉算法：
一般情况下，
Dist[k] = <源点到顶点 k 的弧上的权值 >
或者 = <源点到 其它顶点 的路径长度 >+ <其它顶点 到顶点 k 的 弧上的权值 >
设臵辅助数组 Dist，其中每个分量 Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。
86
在这条路径上，必定只含一条弧，并且这条弧的权值最小。
下一条路径长度次短的最短路径的特点,
路径长度最短的最短路径的特点,
它只可能有两种情况,或者是直接从源点到该点 (只含一条弧 )；
或者是，从源点经过顶点 v1，再到达该顶点 (由两条弧组成 )。
其余最短路径的特点：
再下一条路径长度次短的最短路径的特点,
它可能有三种情况：或者是，直接从源点到该点 (只含一条弧 )；
或者是，从源点经过顶点 v1，再到达该顶点 (由两条弧组成 )；
或者是，从源点经过顶点 v2，再到达该顶点。
它或者是直接从源点到该点 (只含一条弧 )； 或者是，从源点经过已求得最短路径的顶点，再到达该顶点。
87
三、迪 杰斯特拉 (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的路径权值之和 （反证法可证）
88
算法描述：
（ 1） 设 A[n][n]为有向网的带权 邻接矩阵,A[i][j]表示弧 (vi,vj )
权值,S为已找到从源点 v0出发的最短路径的终点集合，它的初始状态为 {v0}.辅助数组 dist[n]为各终点当前找到的最短路径的长度，
它的初始值为 dist[i]＝ A[v0,i] //即邻接矩阵中第 v0行的权值
（ 2） 选择 u，使得
dist[u]＝ min{dist[w]|w∈V -S } //w是 S集之外的顶点
//dist[u]是从源点 v0到 S集外所有顶点的弧中最短的一条
S=S∪{u} //将 u加入 S集
（ 3） 对于所有不在 S中的终点 w，若
dist[u]+ A[u,w]< dist[w] //即 (v0,u)＋ (u,w)<(v0,w)
则修改 dist[w]为,dist[w]＝ dist[u]+ A[u,w]
（ 4） 重复操作 (2),(3)共 n-1次，由此求得从 v0到各终点的最短路径。
89
20 0 10 30 max max max
Dist[7]
▲
20 0 10 30 15 max max
Dist[7]
▲
Path[7][7]
S={b}
(a) Dist和 Path的初始状态，
从中求得从 b到 c的最短路径
b a
cb
b d
Path[7][7]
S={b,c}
(a) 修改 Dist和 Path的值，
从中求得从 b到 e的最短路径
b a
cb
b d
cb e
单元最短路径算法执行过程示例
90
20 0 10 27 15 max 30
Dist[7]
▲
20 0 10 27 15 max 29
Dist[7]
▲
Path[7][7]
S={b,c,e}
(a) Dist和 Path的初始状态，
从中求得从 b到 a的最短路径
b a
cb
Path[7][7]
S={b,c,e,a}
(a) 修改 Dist和 Path的值，
从中求得从 b到 d的最短路径
b a
cb
b c
cb e
单元最短路径算法执行过程示例
ab g
e db c e d
cb e
b c e g
91
20 0 10 27 15 max 29
Dist[7]
▲
20 0 10 27 15 max 29
Dist[7]
▲
Path[7][7]
S={b,c,e,a,d}
(a) Dist和 Path的初始状态，
从中求得从 b到 g的最短路径
b a
cb
Path[7][7]
S={b,c,e,a,d,g}
(a) 修改 Dist和 Path的值，
可见从 b到 f没有路径
b a
cb
b c
cb e
单元最短路径算法执行过程示例
ab g
e db c e d
cb e
b c e g
92
终点 从 v0到各终点的 dist值和最短路径
v1
v2
v3
v4
v5
vj
60
{v0,v2,v3}
50
{v0,v4,v3}
30
{v0,v4}
90
{v0,v4,v5}
60
{v0,v4,v3,v5}
5
5
40
3
1 2
100 60
30
10
10 20
50
s {v0,v2} {v0,v2,v4} {v0,v2,v4,v3} {v0,v2,v4,v3,v5}
10
{v0,v2}
∞
30
{v0,v4}
100
{v0,v5}
∞ ∞ ∞ ∞
例：
v2 v4 v3 v5
100
{v0,v5}0
1
2
3
4
5
dist[w]
0 1 2 3 4 5
与最小生成树的不同点：路径可能是累加的！
10
{v0,v2}
50
{v0,v4,v3}
30
{v0,v4}
(v0,v2)+ (v2,v3)<(v0,v3)S之外的当前最短路径之顶点
93
① AOV网 (Activity On Vertices)—用 顶点 表示活动的网络
AOV网定义,若用有向图表示一个工程，在图中 用顶点表示活动，用弧表示活动间的优先关系。 Vi 必须先于活动 Vj 进行。 则这样的有向图叫做用顶点表示活动的网络，简称 AOV。
② AOE网 (Activity On Edges)—用 边 表示活动的网络
AOE网定义,如果在无环的带权有向图中,用 有向边表示一个工程中的活动，
用边上权值表示活动持续时间，用顶点表示事件,则这样的有向图叫做用边表示活动的网络，简称 AOE。
二、两种常用的活动网络 (Activity Network):
一、何为有向无环图（ DAG 图 ）
实例
L
B
E F G
F G
有向树
B
E F G
L F G
DAG图
B
E F G
L F G
有向图 (含环 )
A B
A B10
AOV网络的用途,我们经常用有向图来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成。
AOV网络若用于教学计划的制定，可以解决哪些课程是必须先修的，哪些课程是可以并行学习的。
7.6 拓扑排序
94
对有向图进行如下操作,
按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。
例如,对于下列有向图
B
DA
C可求得 拓扑有序序列,A B C D 或 A C B D
由此所得顶点的线性序列称之为 拓扑有序序列
B
DA
C
反之，对于下列有向图不能求得它的拓扑有序序列。
因为图中存在一个回路 {B,C,D}
三、什么叫拓扑排序？
对一个有向无环图中的顶点排成一个具有前后次序的线性序列。
7.6 拓扑排序
95
四、如 何进行拓扑排序？
1）从有向图中选取一个没有前驱的顶点，并输出之 ;
重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。
2）从有向图中删去此顶点以及所有以它为尾的弧 ;
在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减 1
a
b
c
g
h
d
f
e
a b h c d g f e
7.6 拓扑排序
96
进行拓扑排序的方法：
1,输入 AOV网络。令 n 为顶点个数。
2,在 AOV网络中 选一个没有直接前驱的顶点,并输出之 ;
3,从图中删去该顶点,同时删去所有它发出的有向边 ;
4,重复以上 2,3 步,直到：
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；
或：
图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV网络中必定存在有向环。
拓扑排序算法,重复选择没有直接前驱的顶点。
97
取入度为零的顶点 v;
while (v<>0) {
printf(v); ++m;
w=FirstAdj(v);
while (w<>0) {
inDegree[w]--;
w:=nextAdj(v,w);
}
取下一个入度为零的顶点 v;
}
if (m<n) printf(―图中有回路” );
算法描述
98
为避免每次都要搜索入度为零的顶点，在算法中设置一个,栈”,
以保存,入度为零” 的 顶点 。
CountInDegree(G,indegree); //对各顶点求入度
InitStack(S);
for ( i=0; i<G.vexnum; ++i)
if (!indegree[i]) Push(S,i); //入度为零的顶点入栈
count=0; //对输出顶点计数
while (!EmptyStack(S)) {
Pop(S,v); ++count; printf(v);
for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){
--indegree(w); // 弧头顶点的入度减一
if (!indegree[w]) Push(S,w); //新产生的入度为零的顶点入栈
}
}
if (count<G.vexnum) printf(―图中有回路” )
99
例课程代号 课程名称 先修棵
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--C7--C9--C10--C11--C6--C12--C8
或,C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个 AOV网的拓扑序列不是唯一的六,拓扑排序举例
100
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
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5
(5)
101
C6
C8
C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
(7)
C6
C8
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10
（ 8）
C6
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7
(6)
C6
C8C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11
(9)
C8C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6
(10)
C8
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6--C12
(11)
（ 11）
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6--C12--C8
(12)
102
7.7 关键路径问题,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。
问,哪些子工程项是“关键工程”？
即,哪些子工程项将影响整个工程的完成期限的。
构造关键路径的方法,要用到拓扑排序和逆拓扑排序
在 AOE网络中,有些活动 顺序进行,有些活动 并行进行 。
从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。
这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。
完成整个工程所需的时间取决于从源点到汇点的最长路径长度，
即在这条路径上所有活动的持续时间之和。 这条路径长度最长的路径就叫做关键路径 (Critical Path)。
103
AOE网络的用途,常用于大型工程的计划管理。 利用 AOE网络可以解决以下两个问题：
(1) 完成整个工程至少需要多少时间。
(假设网络中没有环 )?
(2) 为缩短完成工程所需的时间,应当加快哪些活动?
或者说，哪些活动是影响工程进度的关键？
AOV网定义,若用有向图表示一个工程，在图中 用顶点表示活动，用弧表示活动间的优先关系。 Vi 必须先于活动 Vj 进行。 则这样的有向图叫做用顶点表示活动的网络，
简称 AOV。
104
整个工程完成的时间为,从有向图的 源点 到 汇点的最长路径。
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
7
2
4
4
例如,
关键活动,该弧上的 权值增加 将使有向图上的 最长路径的长度增加。
源点汇点该活动的 最早 开始时间 = 该活动 的 最迟 开始时间
105
假设第 i条弧为 <j,k>,则 对第 i项活动言
“活动 (弧 )‖的最早开始时间 ee(i),ee(i) = ve(j);
―活动 (弧 )‖的最迟开始时间 el(i),el(i) = vl(k)–dut(<j,k>);
事件发生时间的计算公式,
ve(源点 ) = 0; ve(k) = Max{ve(j) + dut(<j,k>)}
vl(汇点 ) = ve(汇点 ); vl(j) = Min{vl(k) – dut(<j,k>)}
事件 (顶点 )的最早发生时间 ve(j):从源点到顶点 j的最长路径长度 ;
事件 (顶点 )的最迟发生时间 vl(k):从顶点 k到汇点的最短路径长度 ;
算法的实现要点,显然,求 ve的顺序应该是按拓扑有序的次序 ; 而求
vl的顺序应该是按拓扑逆序的次序 ; 因为拓扑逆序序列即为拓扑有序序列的逆序列，因此应该在拓扑排序的过程中，另设一个,栈”
记下拓扑有序序列。
Ve(j) 的求法：
V1 VJ
3
5
12
88
Ve(Vj) = 3,5,12,88的最大值 88
起点,
0
V1 VJ
Ve(Vj) = Vj 的起始结点的最早发生时间
+ 各自的边的权值中的和的最大值 88
Vu
Vv
Vw
Vx
2
3
9
82
1
2
3
6
由源点至收点 注意,本图说明由已知的所有的起始结点的 Ve,可得知终止结点的 Ve 。
如：从 Ve(Vu),Ve (Vv),Ve (Vw),Ve
(Vx) 可知 Ve(Vj)
注意,开始时只有源点的 Ve ＝ 0 已知，利用拓扑排序的序列可得到每一个结点的 Ve 。 且结点的 Ve 确定次序和 拓扑排序的序列相同。
关键路径
Vl(j)） 的求法：
Vj Vn
Vl(Vj) = 取 10-2,10-4,10-3,10-7的最小值 3
2
4
3
7
10
10
收点
Vj Vn
Vl(Vj) = 取终止结点的最迟发生时间
- 各自的边的权值的差的最小值 3
10
10
收点
Vu
Vv
Vw
Vx
8
8
5
1
2
1
2
9 由收点至源点注意,本图说明由已知的所有的终止结点的 Vl,可得知起始结点的 Vl 。
如：从 Vl(Vu),Vl (Vv),Vl (Vw),Vl (Vx)
可知 Vl(Vj)
注意,开始时只有收点的 Vl ＝ Ve(Vn) 已知，利用逆拓扑排序的序列可得到每一个结点的 Vl 。 且结点的 Vl 确定次序和逆 拓扑排序的序列相同。
关键路径
108
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
7
2
4
4
a b c d e f g h k
ve
vl
0 0 0 0 0 0 0 0 06 4 5 7 1157 15 14 18
181818181818181818 16 1486 6 1080 7
拓扑有序序列,a - d - f - c - b - e - h - g - k
109
0 6 4 5 7 7 15 14 18
1814161078660
0 0 0 6 4 5 7 7 7 15 14
14160 2 3 6 6 8 8 7 10
ab ac ad be ce df eg eh fh gk hk
权 6 4 5 1 1 2 8 7 4 2 4
e
l
a b c d e f g h k
ve
vl
110
算法描述
输入顶点和弧信息，建立其邻接表
计算每个顶点的入度
对其进行拓扑排序
–排序过程中求顶点的 Ve[i]
–将得到的拓扑序列进栈
按逆拓扑序列求顶点的 Vl[i]
计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动
9
8
7
64
5
3
2
1
a6=2
例 设一个工程有 11项活动,9个事件事件 V1——表示整个工程开始事件 V9——表示整个工程结束
(1) 完成整项工程至少需要多少时间？
(2) 哪些活动是影响工程进度的关键？
111
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
^
112
求关键路径步骤
求 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
113
图存储结构遍 历邻接矩阵邻 接 表十字链表邻接多重表深度优先搜索 DFS
广度优先搜索 DFS
无向图的应用应用图的连通分量图的生成树 最小生成树 Prim算法
Kruskal算法有向 (无环 )图的应用最短路径 Dijkstra算法
Floyd算法
（利用 DFS）
本章小结
(利用 DFS和 BFS)
114
7.8 广义表（ Lists）
① 元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。
② 所有数据元素仍 属同一数据类型 。
广义表的定义广义表的存储结构广义表的遍历广义表的特点,一种特殊的线性表
115
7.8.1 广义表的定义广义表是线性表的推广，也称为列表（ lists）
记为,LS = ( a1,a2,……,an )
广义表名 表头 (Head） 表尾 (Tail)
1、定义：
① 第一个 元素是表头,而其余元素组成的 表称为表尾；
② 用小写字母表示原子类型，用 大写字母 表示列表。
n是表长在广义表中约定：
讨论,广义表与线性表的区别和联系？
广义表中元素既可以是原子类型，也可以是列表；
当每个元素都为原子且类型相同时，就是线性表。
116
广义表是 递归 定义的线性结构，
LS = (?1,?2,,?n )
其中,?i 或为原子 或为广义表例如,A = ( )
F = (d,(e))
D = ((a,(b,c)),F)
C = (A,D,F)
B = (a,B) = (a,(a,(a,,) ) )
117
广义表 LS = (?1,?2,…,?n )的结构特点,
1) 广义表中的数据元素有相对 次序 ;
2) 广义表的 长度 定义为最外层包含元素个数 ;
3) 广义表的 深度 定义为所含括弧的重数 ;
注意,“原子”的深度为 0 ;
“空表”的深度为 1 。
4) 广义表可以 共享 ;
5) 广义表可以是一个 递归 的表 ;
递归表的深度是无穷值，长度是有限值。
118
6) 任何一个非空广义表 LS = (?1,?2,…,?n)
均可分解为表头 Head(LS) =?1 和表尾 Tail(LS) = (?2,…,?n) 两部分例如,D = ( E,F ) = ((a,(b,c)),F )
Head( D ) = E Tail( D ) = ( F )
Head( E ) = a Tail( E ) = ( ( b,c) )
Head( (( b,c)) ) = ( b,c) Tail( (( b,c)) ) = ( )
Head( ( b,c) ) = b Tail( ( b,c) ) = ( c )
Head( ( c ) ) = c Tail( ( c ) ) = ( )
119
E=(a,E)=(a,(a,E))= (a,(a,(a,…….))),E为递归表
1） A =( )
2） B = ( e )
3） C =( a,( b,c,d ) )
4） D=( A,B,C )
5） E=(a,E)
例,求下列广义表的长度。
n=0,因为 A是空表
n=1，表中元素 e是原子
n=2,a 为原子,(b,c,d)为子表
n=3,3个元素都是子表
n=2,a 为原子,E为子表
D=(A,B,C)=(( ),(e),(a,(b,c,d))),共享表
120
A B
D
C
e
a
b c d
② A=( a,(b,A) )
例,试用图形表示下列广义表,
（设 代表原子,代表子表）e
① D=(A,B,C)=( ( ),(e),( a,(b,c,d) ) )
A
a
b
① 的长度为 3，深度为 3 ② 的长度为 2，深度为 ∞
深度＝括号的重数＝ 结点的层数
121
广义表是一个 多层次 的 线性结构例如：
D=(E,F)
其中,
E=(a,(b,c))
F=(d,(e))
D
E F
a ( ) d ( )
b c e
122
7.8.2 广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示,通常用链式结构,每个 元素 用一个结点表示。
1.原子结点,表示原子，可设 2个域或 3个域，依习惯而选。
valuetag=0
标志域 数值域注意：列表的,元素,还可以是列表，所以结点可能有两种形式
tpatomtag=０
标志域 值域 表尾指针法 2：标志域、值域、表尾指针指向下一结点法 1：标志域，数值域
123
tphptag=1
标志域 表头指针 表尾指针
2.表结点,表示列表，若表不空，则可分解为表头和表尾，用
3个域表示,标志域，表头指针，表尾指针。
① A =( )
^1
0 e
③ C =( a,( b,c,d ) )
1 ^1
1
0 b 0 d
1 ^1
例：
② B=( e )
0 a
A=NULL
指向子表 指向下一结点
^^1
0 c
124
⑤ E=(a,E)
④ D=( A,B,C )＝ (( ),(e),(a,(b,c,d)))
0 a
^1
1
^1
1 ^1
1 ^1
10 e 0 a 1 ^1
^1
0 b 0 d0 c
125
1) 表头、表尾分析法,
构造存储结构的两种分析方法,
若表头为原子，则为空表 ls = NIL
非空表 ls tag=1
指向表头的指针指向表尾的指针
tag=0 data
否则，依次类推。
126
L = ( a,( x,y ),( ( x ) ) )a ( x,y ) ( )
1L
= ( )
0 a
1 1
1 1
1
0 x
( )x
127
1 1 1 ls …?
2) 子表分析法,
若子表为原子，则为空表 ls=NIL
非空表指向子表 1
的指针
tag=0 data
否则，依次类推。
指向子表 2
的指针指向子表 n
的指针
128
例如,
ls
((x))
LS=( a,(x,y),((x)) )
a (x,y)
129
广义表从结构上可以分解成广义表 = 表头 + 表尾或者广义表 = 子表 1 + 子表 2 + ··· + 子表 n
因此常利用分治法求解之。
算法设计中的关键问题是,如何将 l
个子问题的解组合成原问题的解。
130
广义表的头尾链表存储表示
typedef enum {ATOM,LIST} ElemTag;
//ATOM==0:原子,LIST==1:子表
typedef struct GLNode {
ElemTag tag; //标志域
union{
AtomType atom; //原子结点的数据域
struct {struct GLNode *hp,*tp;} ptr;
};
} *GList tag=1 hp tpptr表结点
tag=0 data
131
7.8.3 广义表的遍历广义表由遍历分为表头和表尾两部分。
可以直接求解的两种简单情况为,
空表 ;
原子结点可以直接访问。
将广义表分解成表头和表尾两部分，分别
(递归 )遍历求得广义表的每个结点。
132
若 ls= NIL 则 输出（）
若 ls= 原子 则 输出该原子否则输出（,
遍历 表头 ls->ptr.hp
遍历 表尾 ls->ptr.tp
输出 ）；
遍历广义表的算法描述如下,
133
void OutputGList( Glist LS ) {
if (!LS) cout << ―()‖;
else {
if ( LS->tag==ATOM ) cout << LS->data;
else {
cout << ―(―;
p = LS;
while ( p ) {
OutputGList( p->ptr,hp );
p = p->ptr.tp;
if ( p ) cout << ―,‖;
} // while
cout << ―)‖;
}
}
}
134
1,熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。
2,熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、
深度优先搜索和广度优先搜索的算法。应注意图的遍历算法与树的遍历算法之间的类似和差异。
3,应用图的遍历算法求解各种简单路径问题。
4,理解教科书中讨论的各种图的算法。
小结图是一种复杂的非线性结构。本章介绍了图的基本概念，
图的相邻矩阵和邻接表两种常用的存储表示方法，讨论了图的周游,最小生成树、最短路径、拓扑排序及关键路径等问题，并给出了相应的算法。重点是掌握图的存储表示和各种算法的基本思想。
第 7章 图和广义表
2
图（ Graph） 是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，即每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素 之间有着明显的层次关系，虽然每一层上的数据元素可能和下一层中多个元素（孩子） 相关，但只能和上一层中一个元素（双亲）
相关；而在 图形结构中，结点之间 的关系可以是任意的，任意两个数据元素之间都可能相关。
图在各个领域都有着广泛的应用,如电路网络分析、交通运输、
管理与线路的铺设、印刷电路板与集成电路的布线等众多直接与图有关的问题，它们必须用图的有关方法进行处理；另外像工作的分配、工程进度的安排、课程表的制订、关系数据库的设计等许多实际问题，如果间接地用图来表示，处理起来比较方便。这些技术领域都是把图作为解决问题的主要数学手段来使用，因此，如何在计算机中表示和处理图结构，就是计算机科学需研究的一项重要课题。
3
【 学习目标 】
1．领会图的类型定义,
2．熟悉图的各种存储结构及其构造算法,
了解各种存储结构的特点和选用原则,
3．熟练掌握图的两种遍历算法,
4．理解各种图的应用问题的算法,
5.了解广义表的结构和使用
4
【 重点和难点 】
图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法 及其 应用场合 。
【 知识点 】
图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、
无向网的最小生成树、最短路径、拓扑排序、关键路径
5
第七章 习题
基础知识
–P47,7.1 7.5 7.7 7.9 7.10 7.11
作业
–P49,7.22 7.23 7.24 7.28 7.32
–P50,7.36 7.41
6
7.1 图的定义和术语
7.2 图的存储结构
7.3 图的遍历
7.4 连通网的最小生成树
7.5 单源最短路径
7.6 拓扑排序
7.7 关键路径
7.8 广义表
7
7.1 图的基本术语图,记为 G＝ ( V,E )
其中,V 是 G的顶点集合，是有穷非空集；
E 是 G的边 集合，是有穷集。
问：当 E(G)为空时，图 G存在否？
答：还存在！但此时图 G只有顶点而没有边。
有向图：
无向图：
完全图：
图 G中的每条边都是有方向的；
图 G中的每条边都是无方向的；
图 G任意两个顶点都有一条边相连接；
若 n 个顶点的无向图有 n(n-1)/2 条边,称为 无向完全图
若 n 个顶点的有向图有 n(n-1) 条边,称为 有向完全图
V=vertex
E=edge
8
② 完全有向图有 n(n-1)条边。
证明,若是完全有向图，则顶点 1必必与所有其他顶点各有 2条连线，即有 2(n-1)条边,顶点 2有 2(n-2)条边,…,顶点 n-1有 2
条边,顶点 n有 0条边,
总边数＝ 2( n-1＋ n-2＋ … ＋ 1＋ 0)=2(n-1+0)n/2= n(n-1)
① 完全无向图有 n(n-1)/2 条边。
证明,若是完全无向图，则顶点 1必与所有其他顶点各有 1条连线，即有 n-1条边，顶点 2有 n-2条边,…,顶点 n-1有 1条边,顶点
n有 0条边,
总边数＝ n-1＋ n-2＋ … ＋ 1＋ 0=（ n-1+0)n/2= n(n-1)/2
9
例：判断下列 4种图形各属什么类型？
无向 无向图 (树 ) 有向图 有向
n(n-1)/2 条边 n(n-1) 条边
G1的顶点集合为 V(G1)={0,1,2,3}
边集合为 E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
完全图 完全图
10
例
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)}
11
稀疏图：
稠密图：
设有两个图 G＝ (V,E) 和 G’＝ (V’,E’)。若 V’? V 且
E’?E,则称 图 G’ 是 图 G 的 子图 。
子 图：
边较少的图。通常边数 <<n2
边很多的图。无向图中，边数接近 n(n-1)/2；
有向图中，边数接近 n(n-1)
12
带权图,即边上带权的图。其中 权 是指每条边可以标上具有某种含义的数值（即与边相关的数）。
连通图,在 无向图 中,若从顶点 v1到顶点 v2有路径,则称顶点 v1
与 v2是连通的。如果图中任意一对顶点都是连通的,
则称此图是 连通图 。
非连通图的极大连通子图叫做 连通分量 。
＝ 带权图在有向图中,若对于每一对顶点 vi和 vj,都存在一条从
vi到 vj和 从 vj到 vi的路径,则称此图是 强连通图 。
非强连通图的极大强连通子图 叫做 强连通分量 。
强连通图：
网 络：
有两类图形不在本课程讨论之列：
13
邻接点：
有向边 (u,v)称为弧，边的始点 u叫 弧尾,终点 v叫 弧头顶点 v的度 是与它相关联的边的条数。记作 D(v)。
在 有向图 中,顶点的度等于该顶点的 入度 与 出度 之和。
顶点 v 的入度 是以 v 为终点的有向边的条数,记作 ID(v);
顶点 v 的出度 是以 v 为始点的有向边的条数,记作 OD(v)。
若 (u,v) 是 E(G) 中的一条边，则称 u 与 v 互为 邻接顶点弧头和弧尾：
度、入度和出度：
生成树,是一个 极小连通子图,它含有图中全部顶点,但只有 n-1条边 。
如果在生成树上添加 1条边，必定构成一个环。
若图中有 n个顶点，却少于 n-1条边，必为非连通图。
生成森林：
问,当有向图中仅 1个顶点的入度为 0,其余顶点的入度均为 1，此时是何形状？
由若干棵生成树组成，含全部顶点，但构成这些树的边是最少的。
答,是树！而且是一棵有向树！
14
简单路径,路径上各顶点 v1,v2,...,vm 均 不互相重复 。
回 路：
例：
若路径上第一个顶点 v1 与最后一个顶点 vm 重合，则称这样的路径为 回路 或 环 。
路径,在图 G＝ (V,E) 中,若从顶点 vi 出发,沿一些边经过一些顶点 vp1,vp2,…,vpm，到达顶点 vj。则称顶点序列 ( vi vp1
vp2,.,vpm vj ) 为从顶点 vi 到顶点 vj 的 路径 。它经过的边 (vi,
vp1),(vp1,vp2),...,(vpm,vj)应当是属于 E的 边 。
路径长度,非带权图的路径长度是指此路径上边的 条数 ；带权图的路径长度是指路径上各边的 权 之和 。
15
例 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
16
例
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
17
连通图例
2 4 5
1 3 6
强连通图
3
5
6
例非连通图连通分量例
2 4 5
1 3 6
18
CreatGraph(&G,V,VR),//按定义 (V,VR) 构造图
DestroyGraph(&G),//销毁图
LocateVex(G,u); //若 G中存在顶点 u,则返回该顶点在图中位置；否则返回其它信息。
GetVex(G,v); //返回 v 的值。
PutVex(&G,v,value); //对 v赋值 value。
FirstAdjVex(G,v); //返回 v的第一个邻接点 。若该顶点在 G 中没有邻接点,则返回“空”。
NextAdjVex(G,v,w); //返回 v的 (相对于 w的 )下一个邻接点。若是最后一个则返回“空”。
InsertVex(&G,v); //在图 G中增添新顶点 v。
DeleteVex(&G,v); //删除 G中顶点 v及其相关的弧。
InsertArc(&G,v,w); //在 G中增添弧 <v,w>，若 G是无向的,则还增添对称弧 <w,v>。
DeleteArc(&G,v,w); //在 G中删除弧 <v,w>，若 G是无向的,则还删除对称弧 <w,v>。
DFSTraverse(G,v,Visit()); //从顶点 v起深度优先遍历图 G,并对每个顶点调用 Visit一次。
BFSTraverse(G,v,Visit()); //从顶点 v起广度优先遍历图 G,并对每个顶点调用 Visit一次。
结构的建立和销毁
对顶点的访问操作
插入或删除顶点
插入和删除
对邻接点的操作
遍历基本操作
19
7.2 图的存储结构图的特点：非线性结构（ m,n ）
邻接表
邻接多重表
十字链表设计为邻接矩阵链式存储结构：
顺序存储结构,无！ （多个顶点，无序可言）
但可 用 数组 描述元素间关系。
可用多重链表重点介绍,邻接矩阵 (数组 )表示法邻接表 (链式 )表示法
20
一、邻接矩阵 (数组 )表示法
建立一个 顶点表 （记录各个顶点信息） 和一个 邻接矩阵 （表示各个顶点之间关系）。
设图 A = (V,E) 有 n 个顶点，则图的邻接矩阵是一个二维数组
A.Edge[n][n]，定义为：
v1 v2
v3
v5v4
A
例：
邻接矩阵：
A.Edge =
（ v1 v2 v3 v4 v5 ）
v1
v2
v3
v4
v5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
分析 1,无向图的邻接矩阵是 对称 的；
分析 2,顶点 i的 度 ＝第 i 行 (列 ) 中 1 的个数 ；
特别,完全图 的邻接矩阵中，对角元素为 0，其余全 1。
1 1
1 1 1
1 1 1
1 1 1
1 1 1
0
1
1
顶点表：
=
,
),(,,]][[.
否则或者如果
0
><1A EjiEjijiEdge
21
例,有向图的邻接矩阵分析 1,有向图的邻接矩阵 可能是不对称 的。
分析 2,顶点的 出度 =第 i行元素之和,OD( Vi )=?A.Edge[ i ][j ]
顶点的 入度 =第 i列元素之和。 ID( Vi )=? A.Edge[ j ][i ]
顶点的 度 =第 i行元素之和 +第 i列元素之和,
即,TD(Vi)=OD( Vi ) + ID( Vi )
v1 v2
v3 v4
A 邻接矩阵,A.Edge =
( v1 v2 v3 v4 )
v1
v2
v3
v4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
注,在有向图的邻接矩阵中，
第 i行含义：以结点 vi为尾的弧 (即出度边）；
第 i列含义：以结点 vi为头的弧 (即入度边）。
顶点表：
1 1
1
1
0 1 1 0
0 0 0 0
0 0 0 1
1 0 0 0
22
容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
n个顶点需要 n*n个单元存储边 (弧 );空间效率为 O(n2)。 对稀疏图而言尤其浪费空间。
特别讨论,网（即有权图）的邻接矩阵定义为,A.Edge[ i ][ j ]= Wij <vi,vj> 或（ vi,vj） ∈ VR∞ 无边（弧）
v1 v2
v3
v4
N
v5
v6
5
48
9
7
5
5
61
3
以有向网为例：
邻接矩阵,∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
∞∞∞ ∞∞ ∞
N.Edge =
( v1 v2 v3 v4 v5 v6 )
邻接矩阵法 优点：
邻接矩阵法 缺点：
顶点表：
5 7
4
8 9
5 6
5
3 1
∞ 5 ∞ 7 ∞ ∞
∞∞ 4 ∞ ∞ ∞
8 ∞ ∞ 9
∞∞ 5 ∞ ∞ 6
∞∞ 5 ∞ ∞
3 ∞ 1 ∞
23
注,用两个数组分别存储顶点表和邻接矩阵
#define INFINITY INT_MAX //最大值 ∞
#define MAX_VERTEX_NUM 20 //假设的最大顶点数
Typedef enum {DG,DN,AG,AN } GraphKind; //有向 /无向图，有向 /无向网
Typedef struct ArcCell{ //弧（边）结点的定义
VRType adj; //顶点间关系，无权图取 1或 0；有权图取权值类型
InfoType *info; //该弧相关信息的指针
} ArcCell,AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ];
Typedef struct{ //图的定义
VertexType vexs [MAX_VERTEX_NUM ] ; //顶点表，用一维向量即可
AdjMatrix arcs; //邻接矩阵
int vernum,arcnum; //顶点总数，弧（边）总数
GraphKind kind; //图的种类标志
} Mgraph;
图的邻接矩阵存储表示对于 n个顶点的图或网，空间效率 =O(n2)
24
Status CreateUDN(Mgraph &G) { //无向网的构造，用邻接矩阵表示
scanf(&G.vexnum,&G.arcnum,&IncInfo); //输入总顶点数，总弧数和信息
for(i=0;i<G.vexnum,;++i) scanf(&G.vexs[i] );//输入顶点值，存入一维向量中
for (i=0; i<G.vexnum; ++i) //对邻接矩阵 n*n个单元初始化,adj=∞,info=NULL
for(j=0;j<G.vexnum;++j) G.arcs[i][j]={INFINITY,NULL};
for (k=0;k<G.arcnum;++k){ //给邻接矩阵有关单元赋初值 (循环次数＝弧数
scanf(&v1,&v2,&w); //输入弧的两顶点以及对应权值
i=LocateVex(G,v1); j=LocateVex(G,v2); //找到两顶点在矩阵中的位臵 (n次?
G.arcs[i][j].adj=w; //输入对应权值
if(IncInfo) Input(*G.arcs[i][j].info); //如果弧有信息则填入
G.arcs[i][j] = G.arcs [j] [i]； //无向网是对称矩阵
}
return OK;
} //CreateUDN
例：用邻接矩阵 生成无向网 的算法对于 n个顶点 e条弧的网，
建网时间效率 = O(n2+n+e*n)
25
二、邻接表 (链式 )表示法
对每个顶点 vi 建立一个 单链表,把与 vi有关联的 边的信息 （即度或出度边） 链接 起来，表中每个结点都设为 3个域；
每个单链表还应当附设一个 头结点 （设为 2个域），存 vi信息；
adjvex nextarc infodata firstarc
表结点头结点邻接点域,表示 vi一个邻接点的 位臵链域,指向
vi下一个边或弧的结点数据域,与边有关信息
（如权值）
数据域,存储顶点 vi 信息链域,指向单链表的第一个结点
每个单链表的 头结点另外用顺序存储结构 存储。
26
例：无向图的邻接表
v1 v2
v3
v5v4
邻接表
0
1
2
3
4
^13
34 ^1
4 2 ^0
例：有向图的邻接表
v1 v2
v3 v4
V4
V3
^V2
V1 2
^3
^0
^1
邻接表 (出边 )
注,邻接表不唯一，因各个边结点的链入顺序是任意的。
v1
v2
v3
v4
v5 23 ^1
4 2 ^0
当邻接表的存储结构形成后，
图便唯一确定！
27
分析 1,对于 n个顶点 e条边的无向图,邻接表中除了 n个头结点外，只有 2e个表结点,空间效率为 O(n+2e)。
若是稀疏图 (e<<n2)，则比邻接矩阵表示法 O(n2)省空间。
邻接表存储法的特点：
分析 2,在 有向图 中,邻接表中除了 n个头结点外,只有 e个表结点,
空间效率为 O(n+e)。 若是稀疏图，则比邻接矩阵表示法合适。
—它其实是对邻接矩阵法的一种改进怎样计算无向图顶点的度？
邻接表的 缺点：
怎样计算有向图顶点的出度？
怎样计算有向图顶点的入度？
怎样计算有向图顶点 Vi的度,需遍历全表邻接表的 优点：
TD( Vi )=单链表中链接的结点个数
OD( Vi )＝ 单链出边表中链接的结点数
I D( Vi ) ＝ 邻接点为 Vi的弧个数
TD( Vi ) = OD( Vi ) + I D( Vi )
空间效率高； 容易寻找顶点的邻接点；
判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
28
讨论：邻接表与邻接矩阵有什么异同之处？
联系,邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数 。
区别：
① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但 邻接表不唯一 （链接次序与顶点编号无关）。
② 邻接矩阵的空间复杂度为 O(n2),而邻接表的空间复杂度为 O(n+e)。
用途,邻接矩阵多用于稠密图的存储 (e接近 n(n-1)/2)；而邻接表多用于稀疏图的存储 (e<<n2)
29
图的邻接表存储表示
#define MAX_VERTEX_NUM 20 //假设的最大顶点数
Typedef struct ArcNode {
int adjvex; //该弧所指向的顶点位臵
struct ArcNode *nextarcs; //指向下一条弧的指针
InfoArc *info; //该弧相关信息的指针
} ArcNode；
Typedef struct VNode{ //顶点结构
VertexType data; //顶点信息
ArcNode * firstarc; //指向依附该顶点的第一条弧的指针
} VNode,AdjList[ MAX_VERTEX_NUM ];
Typedef struct { //图结构
AdjList vertics ; //应包含邻接表
int vexnum,arcnum; //应包含顶点总数和弧总数
int kind; //还应说明图的种类（用标志）
} ALGraph; //图结构空间效率为 O(n+2e)或 O(n+e)
时间效率为 O(n+e*n)
30
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
31
一、深度优先搜索二、广度优先搜索
7.3 图的遍历遍历定义,从已给的连通图中某一顶点出发,沿着一些边访遍图中所有的顶点,且使每个顶点仅被访问一次,就叫做 图的遍历,它是 图的 基本运算。
遍历实质,找每个顶点的邻接点的过程。
图的特点,图中可能存在 回路,且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点 。
解决思路,可设臵一个 辅助数组 visited [n ]，用来标记每个被访问过的顶点。它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 i被访问，就立即改 visited [i]为 1，防止它被多次访问。
图常用的遍历：
怎样避免重复访问？
32
V1
V2 V3
V4 V5 V6 V7
V8
V1
V2 V3
V4 V5 V6 V7
V8
深度优先搜索 (DFS)
V1 V2 V4 V8 V5 V3 V6 V7
生成树遍历序列广度优先搜索 (BFS)
V1V2V3V4V5V6V7V8
最短路径！
图的遍历 -例子
33
一、深度优先搜索 ( DFS )
基本思想,——仿树的先序遍历过程 。
Depth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
DFS 结果例 1：
→ → → →
→ → →
v2 v4 v8
v5 v3 v6 v7
例 2：
v2 → v1 → v3 → v5 →
DFS 结果
v4 → v6
起点起点遍历步骤
1、深度优先搜索,
有向图的实例,为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。
如：结点 5的邻接结点有两个 6,7，则先访问结点 6，再访问结点 7。
5
6
7
2
4
1
3
5
6 7
2
3
1
4
·
·
·
· ·
·
·
从结点 出发的搜索序列：
5,6,2,3,1,4,7
适用的数据结构：栈
5
1
2
43
·
·
· ·
从结点 出发的搜索序列：
1,2,3,4没有搜索到所有的结点，必须另选图中未访问过的结点，
继续进行搜索。
1
35
一、深度优先搜索遍历图连通图的深度优先搜索遍历,从图中某个顶点 V0 出发，访问此顶点，然后依次从 V0的 各个未被访问的 邻接点出发深度优先搜索遍历图,直至图中所有和 V0有路径相通的顶点都被访问到。
SG1 SG2 SG3
W1,W2和 W3均为 V 的邻接点,SG1,SG2 和 SG3 分别为含顶点 W1,W2和 W3
的子图。
访问顶点 V ;
for (W1,W2,W3 )
若 该邻接点 W未被访问,
则 从它出发进行深度优先搜索遍历。
V
w1 w3w2
1,从深度优先搜索遍历连通图的过程类似于树的先根遍历 ;
解决的办法是,为每个顶点设立一个,访问标志 visited[w]”;
2,如何判别 V的邻接点是否被访问？
36
深度优先搜索（遍历）步骤：
详细归纳：
在访问图中某一起始顶点 v后,由 v出发,访问它的任一邻接顶点 w1；
再从 w1出发,访问与 w1邻接但还未被访问过的顶点 w2；
然后再从 w2出发,进行类似的访问,…
如此进行下去,直至到达所有的邻接顶点都被访问过的顶点 u 为止。
接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。
如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问；
如果没有,就 再退回一步 进行搜索。
重复上述过程,直到连通图中所有顶点都被访问过为止。
简单归纳：
访问起始点 v;
若 v的第 1个邻接点没访问过，深度遍历此邻接点；
若当前邻接点已访问过，再找 v的第 2个邻接点重新遍历。
37
讨论 1：计算机如何实现 DFS？
1 2 3 4 5 6
1 0 0 0 0 0 0
2 0 0 0 0 0 0
3 0 0 0 0 0 0
4 0 0 0 0 0 0
5 0 0 0 0 0 0
6 0 0 0 0 0 0
0
0
0
0
0
0
1
2
3
4
5
6
0
1
0
0
0
0
1
1
0
0
0
0
1
1
1
0
0
0
DFS 结果邻接矩阵
A
辅助数组 visited [n ]
起点
v2→v1→v3→v5→ v4→v6
——开辅助数组 visited [n ]！
例：
1 1 1
1 1
1 1
1 1
1 1
1
1
1
1
0
1
0
1
1
1
1
1
0
1
1
1
1
1
1
38
讨论 2,DFS算法如何编程？
DFS1(A,n,v) {
visit（ v） ;
visited[v]=1;
for( j=1; j<=n; j++)
if ( A[v,j] && ! visited[j] ) DFS1(A,n,j);
return;
}
——可以用递归算法！
//A[n][n]为邻接矩阵,v为起始顶点 (编号）
//访问（例如打印）顶点 v
A[v,j] ＝ 1
有邻接点
visited [n ]=0
未访问过
//访问后立即修改辅助数组标志
//从 v所在行从头搜索邻接点建议,在递归函数中增加一计数器 sum，初值为 n，每访问一次就减 1,减到 0则 return，可避免递归时间过长。
39
讨论 3：在图的邻接表中如何进行 DFS？
v0 → v1 → v2 → v3
DFS 结果
0
0
0
0
0
1
2
3
辅助数组 visited [n ]
例：
—照样借用 visited [n ]！
起点
0
1
2
3
注意,在邻接表中，并非每个链表元素（表结点）都被扫描到,遍历速度很快。
1
0
0
0
1
1
0
0
1
1
1
0
1
1
1
1
40
讨论 4：邻接表的 DFS算法如何编程？
DFS2(List,v,p) {
visit（ v） ;
visited[v]=1;
p=p->link;
if (!p) return;
v=p->data;
while ( !visited[v] ) DFS2(list,v,p);
return;
}
//List为邻接表,v为起始顶点 (编号），
//p为 v所在那条单链表的的头指针。
//访问后立即修改辅助数组标志
//若指针为空，则结束本次遍历
//指向 v的链表中下一邻接点
//取出链表中当前邻接点
——仍可用递归算法
41
void DFSTraverse(Graph G,Status (*Visit)(int v)) {
// 对图 G 作深度优先遍历。
VisitFunc = Visit;
for (v=0; v<G.vexnum; ++v)
visited[v] = FALSE; // 访问标志数组初始化
for (v=0; v<G.vexnum; ++v)
if (!visited[v]) DFS(G,v);
//对尚未访问的顶点调用 DFS
}
首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。
非连通图的深度优先搜索遍历
42
void DFS(Graph G,int v) {
// 从顶点 v出发,深度优先搜索遍历连通图 G
visited[v] = TRUE; VisitFunc(v);
for (w=FirstAdjVex(G,v);
w!=0; w=NextAdjVex(G,v,w))
if (!visited[w]) DFS(G,w);
//对 v的尚未访问的邻接顶点 w递归调用 DFS
} // DFS
时间复杂性：
邻接矩阵,O(n2)
邻接表,O(n+e)
n：结点数
e,边数结论：
稠密图 适于在邻接矩阵上进行深度遍历；
稀疏图 适于在邻接表上进行深度遍历。
43
a b
c
h
d e
k
f
g
8
1
2 3 4 5
6
7
0
F F F F F F F F F
0 1 2 3 4 5 6 7 8
T T T T T T T T T
a c h d k f e b g
访问标志,
访问次序,
例如,a
c
h
d k
f e
44
二、广度优先搜索 ( BFS )
基本思想,——仿树的层次遍历过程 。
Breadth_First Search
v1
v1
v2 v3
v8
v7v6v4 v5
BFS 结果,例：
→ →
→
→v2 v3
→v4 v5 →v6 v7→ v8
例：
v3 →
BFS 结果,
v4 → v5 →
起点遍历步骤起点
v2 → v1 → v6 →
v9 → v8 → v7
无向图的实例,为了说明问题，邻接结点的访问次序以序号为准。序号小的先访问。
结点 1的邻接结点有三个 2,12,11，则先访问结点 2,11，再访问结点 12。
广度 (宽度 )优先搜索,
图的广度优先的访问次序：
1,2,11,12,3,6,7,10,4,5,8,9
适用的数据结构：队列
1
2 12 11
3 6 7 10
4 5 8 9
1
2 1211
3 6 7 10
4 5 8 9
·
·
·
·
·
·
· ·
· ·
· ·
队列的变化：
广度（宽度）优先搜索,
A
B C D
E F G H I J K
L
树的按层次进行访问的次序：
A,B,C,D,E,F,G,H、
I,J,K,L
适用的数据结构：队列
A
B C D
1、结点 A进队
2、结点 A出队、访问，队空
3、结点 A的儿子结点进队
4,结点 B出队、访问
5、结点 B的儿子结点进队
6、结点 C出队、访问
7、结点 C的儿子结点进队
C D
E F GC D
E F GD
E F GD H
47
广度优先搜索（遍历）步骤简单归纳：
在访问了起始点 v之后，依次访问 v的邻接点；
然后再依次访问这些顶点中未被访问过的邻接点；
直到所有顶点都被访问过为止。
广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。
48
讨论 1：计算机如何实现 BFS？
邻接表
——除辅助数组 visited [n ]外，
还需再开一辅助队列！例：
起点辅助队列
v2已访问过了
BFS 遍历结果入队！
初始 f=n-1,r=0
49
讨论 2,BFS算法如何编程？
BFS1(List,n,v) {
Visit(v); Visited[v]=1;
front=n-1; rear=0; q[rear]=v;
while(rear!=front) {
front=(front+1)%n; v=q[front];
p=List[v].firstarc;
while ( !p ) {
if(! Visited[adjvex(p)] ) {
Visit(adjvex(p)); Visited[adjvex(p)]=1;
rear=(rear+1)%n; q[rear]= adjvex(p)}
p=nextarc(p);
}
}
return
}
——层次遍历应当用队列！
//List为邻接表,v为起点,Q[n]为辅助队列
//访问（例如打印）顶点 v并修改标志
//指向单链表中下一个邻接点
//队列指针初始化
//起始点入队
//队不空时
//访问过的顶点出队
//P指向第 1个邻接点
//未到表尾，且邻接域未访问过，
//则先输出再改标
//记，最后再入队图的广度遍历程序使用的变量说明,Boolean visited[MAX];//用于标识结点是否已被访问过
Status (*VisitFunc)(int v); //函数变量
void BFSTraverse( Graph G,Status ( * VisitFunc) (int v));
{ VisitFunc = Visit;
for (v=0;v<G.vexnum;++v) visited[v]=FALSE;
InitQueue(Q);
for (v=0; v<G.vexnum; ++v)
if (!Visited[v]) {
Visited[ v ] = TRUE; Visit(v); EnQueue(Q,v);
while (!EmptyQueue(Q)) {
DeQueue(Q,u);
for (w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
if (!Visited[w]) {
Visited[v] =TRUE; Visit(v); EnQueue(Q,w)
} ;
}
}
}
时间复杂性：
邻接矩阵,O(n2)
邻接表,O(n+e)
n：结点数
e,边数
51
BFS 算法效率分析,
DFS与 BFS之比较：
空间复杂度相同，都是 O(n)(借用了堆栈或队列）；
时间复杂度只与存储结构（ 邻接矩阵或邻接表 ）有关，
而与搜索路径无关。
如果使用邻接表来表示图，则 BFS循环的总时间代价为
d0 + d1 + … + d n-1 = O(e),其中的 di 是顶点 i 的度 。
如果使用邻接矩阵，则 BFS对于每一个被访问到的顶点，
都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为 O(n2)。
（设图中有 n 个顶点,e 条边）
52
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdatafirstarc
5
5
4 3 ^
^
^
adjvexnext
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
图的广度遍历演示
53
例 1
42 3
5
1
2
3
4
1
3
4
2
vexdatafirstarc
5
5
4 3 ^
^
^
adjvexnext
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
54
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
vexdatafirstarc
5
5
4 3 ^
^
^
adjvexnext
5 5
1 ^5
1
1
4 3 ^
2
2
55
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0 1 2 3 4 5 6 7
迷宫及其最短历经求迷宫的最短路径迷宫简介迷宫可用一个二维位数组表示,0表示连通,1表示不连通。连通方向又分为 4连通和八连通两种。
如下图所示，右图表示了一个八连通的所有方向所形成的有向图。
...
.,
.,,,,.
...,
..,,...
.,
表示迷宫的方向图最后形成有向图
56
g = i+di[v]
h = j+di[v]
v = 0,1,2,3,4,5,6,7
（ 1）如何得到和迷宫相应的有向图求迷宫的最短路径
di 0 1 1 1 0 -1 -1 -1
dj 1 1 0 -1 -1 -1 0 1
下标增量数组
i-1,j-1 i+1,j-1 i-1,j+1
i,j+1
i+1,j+1
i,j
i+1,ji+1,j-1
i,j-1
8个相邻位置的坐标
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0 1 2 3 4 5 6 7
迷宫及其最短历经
...
.,
.,,,,.
...,
..,,...
.,
表示迷宫的方向图
57
0
1
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
1
1
1
0
1
0
1
0
1
0
1
1
0
0
0
1
0
1
0
0
1
1
0
0
0
1
0
1
1
1
0
0
1
0
1
1
0
0 1 2 3 4 5 6 7
（ 2）如何得到路径求迷宫的最短路径
0,0^ 0,0 0,0 0,0 0,0 0,0 0,0 ^
最短路径搜索过程中的路径
Q.front
Q.rear
0 2 6 6 6
5 721
2
5 6 7 7 7
4 4 5 6
653 4
3 4
最短路径的搜索过程
...
.,
.,,,,.
...,
..,,...
.,
表示迷宫的方向图
58
数据结构：
求迷宫的最短路径程序：
链式队列：纪录搜索过程堆栈：保存结果求 m行 n列的迷宫 maze中从入口 [0][0]到出口 [m-1][n-1]的最短路径，若存在，
则返回 TRUE，此时栈 S中从栈顶到栈底为最短路径所经过的各个方位 ;若该迷宫不通，则返回 FALSE，此时栈 S为空栈。
该路口可行条件：
若 0<=npos,xpos<m-1,
0<=npos,ypos<n-1,
Maze[npos.xpos][npos.ypos]==0,
visited[npos.xpos][npos.ypos]==FALSE
则 Pass函数为 TRUE,否则为 FALSE
堆栈操作程序最短路径程序迷宫搜索程序队列处理程序堆栈数组：表示迷宫、已到位置和方向
59
ypedef struct { int xpos; int ypos; } PosType;
typedef struct DQNode {
PosType seat;
struct DQNode *next;
DQNode *pre;
} DQNode,*DQuencePtr;
typedef struct { DQuencePtr fronr; DQuencePtr rear; } DLinkQuence;
void InitQuence( DLinkQuence &Q ) { Q,front = NULL; Q.rear = NULL; }
void EnQuence( DLinkQuence &Q,PosType e ) {
p = new DQNode;
p->seat.xpos = e.xpos;
p->seat.ypos = e.ypos;
p->next = NULL;
if (!Q.rear) { p->pre = NULL; Q.rear = p; Q.front = p; }
else { p->pre = Q->front; Q.rear-?next = p; Q.rear = p; }
}
void GetHead( DLinkQuence Q,PosType &e ) {
e.ypos = Q.front->seat.ypos; e.xpos = Q.front->seat.xpos;
}
void DeQuence( DLinkQuence &Q ) { Q.front = Q.Front->next; }
void QuenceEmpty( DLinkQuence Q ) { return (Q.front == NULL); }
60
bool ShortestPath(int maze[][],int m,int n,Stack &S)
{ DLinkQueue Q;
bool visited[m][n];
InitQueue(Q); // 队列初始化
for(i=0; i<m; i++) // 对访问标志数组置初值
for(j=0; j<n; j++) visited[i][j] = FALSE;
if (maze[0][0]!=0) return FALSE;
e.xpos = 0; e.ypos = 0; EnQueue(Q,e); found = FALSE;
while(!found && !QueueEmpty(Q)) {
GetHead(Q,curpos); // 取当前的队头顶点 curpos
for (v=0; v<8,!found; v++) { // 搜索 8个方向的邻接点
npos = NextPos(curpos,v); // 类型为 PosType的 npos是搜索到的下一点
if (Pass(npos)) { // 如果下一点可走通则入队列
EnQueue(Q,npos); visited[npos.xpos][npos.ypos] = TRUE;
}//if
if (npos.xpos=n-1 && npos.ypos=m-1) found=TRUE; // 找到出口
}//for
DeQueue(Q); // 出队列，准备从下一邻接点搜索
}//while
if (found) {
InitStack(S); p = Q.rear; // 从出口顶点以 pre指针为导向，反向查看
while(!p) { Push(S,p->seat); p=p->pre; } //while
return TRUE;
}//if
else return FALSE;
}//ShortestPath
时间复杂度,O(m*n)
int Pass( PosType npos )
{
if ( npos,xpos>=0 && npos.xops<m-1 &&
npos,ypos>=0 && npos.ypos<n-1 &&
Maze[npos.xpos][npos.ypos]==0 &&
visited[npos.xpos][npos.ypos]==FALSE ) return TRUE;
else return FALSE;
}
61
生成树,是一个极小连通子图，它含有图中全部顶点，但只有
n-1条边。
生成森林,由若干棵 生成树 组成，含全部顶点，但构成这些树的边是最少的。
思考 1：对连通图进行遍历，得到的是什么？
—得到的将是一个极小连通子图，即图的 生成树 ！
由深度优先搜索得到的生成树，称为深度优先搜索生成树。
由广度优先搜索得到的生成树，称为广度优先搜索生成树。
思考 2：对非连通图进行遍历，得到的是什么？
— 得到的将是各连通分量的生成树，即图的 生成森林 ！
7.4 连通图的小生成树求图的生成树生成树的特征 —n个顶点的 连通 网络的生成树有 n个顶点,n-1条边。
求生成树的方法 —DFS(深度优先搜索 )和 BFS(广度优先搜索 )
62
欲在 n个城市间建立通信网，则 n个城市应铺 n-1条线路；但因为每条线路都会有对应的经济成本，而 n个城市可能有 n(n-1)/2条线路，那么,如何选择 n–1条线路，使总费用最少？
典型用途：
数学模型：
顶点 ———表示城市，有 n个；
边 ————表示线路，有 n–1条；
边的权值 —表示线路的经济代价；
连通网 ——表示 n个城市间通信网。
显然此连通网是一个生成树！
问题抽象,n个顶点的生成树很多，需要从中选一棵 代价最小 的生成树，即该树 各边的代价之和 最小 。 此树便称为最小生成树
MST(Minimum cost Spanning Tree)
63
例：画出下图的生成树
DFS
生成树
v0 v1
v2
v4v4v3
邻接表
0
1
2
3
4
^13
34 ^1
4 2 ^0
v4
v3
v2
v1
v0
23 ^1
4 2 ^0
v0
v2
v1
v4
v3 BFS
生成树
v0
v1v3
v2v4
无向连通图
64
有多种算法，但最常用的是以下两种：
最小生成树的 MST 性质如下：
Kruskal（克鲁斯卡尔）算法
Prim（普里姆）算法
Kruskal算法特点,将边归并,适于求 稀疏网 的最小生成树。
Prime算法特点,将顶点归并,与边数无关，适于 稠密网。
这两个算法，都是利用 MST 性质来构造最小生成树的。
若 U集是 V的一个非空子集，若 (u0,v0)是一条 最小权值的边,其中
u0?U,v0?V-U；则,(u0,v0)必在最小生成树上 。
应用,n个城市建网，如何选择 n–1条线路，使总费用最少？
求最小生成树目标,在网的多个生成树中，寻找一个 各边权值之和最小 的生成树。
65
步骤,
(1) 首 先构造一个只有 n个顶点但没有边的非连通图 T={V,?},
图中每个顶点自成一个连通分量。
(2) 当在边集 E 中选到一条具有最小权值的边时,若该边的两个顶点落在 T中不同的连通分量上，则将此边加入到生成树的边集合 T 中；否则将此边舍去，重新选择一条权值最小的边。
(3) 如此重复下去，直到所有顶点在同一个连通分量上为止。
此时的 T即为所求（ 最小生成树 ）。
一、克鲁斯卡尔 (Kruskal)算法设 N ={V,E }是有 n个顶点的连通网，
Kruskal算法采用 邻接表 作为图的存储表示
66
例：应用克鲁斯卡尔算法构造最小生成树的过程
√
√
√ √
×
√
×
√
67
Kruskal（克鲁斯卡尔）算法例,1
4
65
2 3
1
56
55
463
6
2
15
43 2
1
3
5
2 4
6
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
12
7
8
例如,
68
计算机内怎样实现 Kruskal算法？
设计思路：
① 设每条边对应的结构类型为：
特点,将 边 归并 ——适于求 稀疏网 的最小生成树。
故采用 邻接表 作为图的存储表示 。
Lchild vi vj weight Rchild
② 取堆顶元素，加入到对应最小生成树的新邻接表中（初始为空），从堆中删除它并重新排序堆，每次耗时 log2(e)；
③ 重复上一步，注意每次加入时要判断是否,多余,（即是否已被新表中的连通分量包含）；
④ 直到堆空。
显然,Kruskal算法的时间效率＝ O(elog2e)
初态,按权值排序 (以 堆排序 为佳，堆顶即为权值最小的边）
69
算法描述,
构造非连通图 ST=( V,{ } );
k = i = 0; // k 计选中的边数
while (k<n-1) {
++i;
检查边集 E 中第 i 条权值最小的边 (u,v);
若 (u,v)加入 ST后不使 ST中产生回路，则输出边 (u,v); 且 k++;
}
最小代价生成树
1
2 43
5 6
6 1
6
5
5 5
63 4 2
1
2 43
5 6
1
5
3 4 2
5
5
最小代价生成树（简称：最小生成树）
实例的执行过程
1
2 43
5 6
6 1
6
5
5 5
63 4 2
图 G
1、初始连通分量,{1},{2},{3},{4},{5},{6}
2、反复执行添加、放弃动作。 条件：边数不等于 n-1时边 动作 连通分量
(1,3) 添加 {1,3},{4},{5},{6},{2}
(4,6) 添加 {1,3},{4,6},{2},{5}
(2,5) 添加 {1,3},{4,6},{2,5}
(3,6) 添加 {1,3,4,6},{2,5}
(1,4) 放弃 因构成回路
(3,4) 放弃 因构成回路
(2,3) 添加 {1,3,4,5,6,2}
最小代价生成树
1
2 43
5 6
1
5
3 4 2
5
5
算法实现要点,每个结点增加一个数据场，用于标识该结点所属的集合。可用于判断新的边加入后是否构成回路。
71
（ 0）用顶点数组和边数组存放顶点和边信息
（ 1）初始时，令每个顶点的 set互不相同；每个边的 flag为 0
（ 2）选出权值最小且 flag为 0的边
（ 3）若该边依附的两个顶点的 set 值不同，即非连通，则令该边的 flag=1,选中该边；再令该边依附的两顶点的集合以及两集合中所有顶点的 set相同若该边依附的两个顶点的 set值相同，即连通，则令该边的 flag=2,即舍去该边
（ 4）重复上述步骤，直到选出 n-1条边为止顶点结点：
typedef struct
{ int data; //顶点信息
int set;
} VEX;
边结点：
typedef struct
{ int vexs,vexe; //边依附的两顶点
int score; //边的权值
int flag; //标志域
} EDGE;
72
例 1
65
4
3
2
6 5
1
3
5
6
6
4 2
5
data set
1
2
4
5
3
6
1
2
4
5
3
6
1
2
4
5
3
6
vexs score
1
1
2
2
1
3
2
3
3
5
4
4
vexe 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
73
取图中任意一个顶点 v作为生成树的根,之后往生成树上添加新的顶点 w。 在添加的顶点 w和已经在生成树上的顶点 v之间必定存在一条边,并且该边的权值在所有连通顶点 v和 w之间的边中取值最小。
之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止。
二、普里姆 (Prim)算法一般情况下所添加的顶点应满足下列条件,在生成树的构造过程中，图中 n 个顶点分属两个集合,已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集 V-U，则应在所有连通 U中顶点和 V-U
中顶点的边中选取权值最小的边。
U
V-U
74
（ 1）初始状态,U ={u0 },（ u0∈ V）,TE={ },
（ 2）从 E中选择顶点分别属于 U,V-U两个集合、且权值最小的边 （ u0,v0),将顶点 v0归并到集合 U中，边 （ u0,v0)
归并到 TE中；
（ 3）直到 U=V为止。此时 TE中必有 n-1条边,T＝ (V,{TE})
就是最小生成树。
设,N =（ V,E）是个连通网，
另设 U为最小生成树的顶点集,TE为最小生成树的边集。
构造步骤,
普利姆 (Prim)算法
75
例 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
76
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
12
7
例如,
所得生成树权值和 =14+8+3+5+16+21 = 67
例,1
4
65
2 3
1
56
55
463
6
2
3
6
42
5
1
[注 ],在最小生成树的生成过程中，所选的边都是一端在
V-U中，另一端在 U中。
77
设计思路：
① 增设一辅助数组 Closedge[n],每个 数组分量都 有两个域：
要求,使 Colsedge[i].lowcost = min((u,vi)) u?U
计算机内怎样实现 Prim（普里姆）算法？
Prime算法特点,将顶点归并,与边数无关，适于稠密网。
故采用 邻接矩阵 作为图的存储表示。
adjvex lowcost
vi在 U中的邻点 u
Colsedge[i]
V-U中顶点 vi u与 vi之间对应的边权从 u1~un中挑
78
vex
lowcost
vex
lowcost
vex
lowcost
vex
lowcost
vex
lowcost
vex
lowcost
V-UU65432vclosedge
1
42 3
5 6
16 5
5 5
3 6 4 2
6
具体示例：
{1} {2,3,4,5,6}
1
6
1
1
1
5
1
∞
1
∞
{1,3} {2,4,5,6}035 15
3
6
3
4
{1,3,6} {2,4,5}35 0 62 36 0
{1,3,
6,4} {2,5}
3
5 0
3
60 0
{1,3,6,
4,2} {5}0 0 0 0
2
3
0 0 0 0 0
{1,3,6,
4,2,5} {}
起点
5
3
1
2
3
4
5
6
显然,Prim算法的时间效率＝ O(n2)
79
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
12
7
closedge
0 1 2 3 4 5 6
Adjvex
Lowcost
a a a
19 14 18
例如,
e
12
e e
8 16
d
3
d d
7 21
c
5
19 m m 14 m 18
19 5 7 12 m m
m 5 3 m m m
m 7 3 8 21 m
14 12 m 8 m 16
m m m 21 m 27
18 m m m 16 27
80
普里姆算法 克鲁斯卡尔算法时间复杂度 O(n2) O(eloge)
稠密图 稀疏图算法名适应范围比较两种算法
81
7.5 求最短路径两种常见的最短路径问题：
一,单源最短路径 —用 Dijkstra（迪杰斯特拉） 算法二、所有顶点间的最短路径 —用 Floyd（弗洛伊德）算法典型用途,交通问题。如：城市 A到城市 B有多条线路，但每条线路的交通费（或所需时间）不同，那么,如何选择一条线路，使总费用（或总时间）最少？
问题抽象,在 带权有向图 中 A点（源点）到达 B点（终点）的多条路径中，寻找一条 各边权值之和最小 的路径，即最短路径。
（注：最短路径与最小生成树不同，路径上不一定包含 n个顶点）
任意两顶点之间一顶点到其余各顶点
82
一、最短路径用带权的有向图表示一个交通运输网，图中：
顶点 ——表示城市边 ——表示城市间的交通联系权 ——表示此线路的长度或沿此线路运输所花的时间或费用等问题,从某顶点出发，沿图的边到达另一顶点所经过的路径中，
各边上权值之和最小的一条路径 ——最短路径
– 从某个源点到其余各顶点的最短路径
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
83
二、单源最短路径 (Dijkstra算法 )
目的,设一有向图 G=(V,E)，已知各边的权值，以某指定点 v0
为源点，求从 v0到图的其余各点的最短路径。 限定各边上的权值大于或等于 0。
例 1：
源点从 F→A 的路径有 4条：
① F→A,24
② F→B→A,5＋ 18=23
③ F→B→C→A,5+7+9=21
④ F→D→C→A,25+12+9=36
又：
从 F→B 的最短路径是哪条？
从 F→C 的最短路径是哪条？
84
v0 (v0,v1) 10
源点 终点 最 短 路 径 路径长度
(v0,v1,v2) (v0,v3,v2)
(v0,v 3) 30
v1
v2
v3
v4 100(v0,v4) (v0,v3,v4)(v
0,v3,v2,v4)
例：
60
0
1
2
3
4
50
90 70
讨论：计算机如何自动求出这些最短路径？
(v0,v1,v2,v4) 60
85
求 从源点到其余各点的最短路径 的算法的基本思想,
依 最短路径的长度 递增的次序求得各条路径源点
v1
…
其中,从源点到顶点 v的最短路径 是所有最短路径中长度最短者。
v2
求最短路径的迪杰斯特拉算法：
一般情况下，
Dist[k] = <源点到顶点 k 的弧上的权值 >
或者 = <源点到 其它顶点 的路径长度 >+ <其它顶点 到顶点 k 的 弧上的权值 >
设臵辅助数组 Dist，其中每个分量 Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。
86
在这条路径上，必定只含一条弧，并且这条弧的权值最小。
下一条路径长度次短的最短路径的特点,
路径长度最短的最短路径的特点,
它只可能有两种情况,或者是直接从源点到该点 (只含一条弧 )；
或者是，从源点经过顶点 v1，再到达该顶点 (由两条弧组成 )。
其余最短路径的特点：
再下一条路径长度次短的最短路径的特点,
它可能有三种情况：或者是，直接从源点到该点 (只含一条弧 )；
或者是，从源点经过顶点 v1，再到达该顶点 (由两条弧组成 )；
或者是，从源点经过顶点 v2，再到达该顶点。
它或者是直接从源点到该点 (只含一条弧 )； 或者是，从源点经过已求得最短路径的顶点，再到达该顶点。
87
三、迪 杰斯特拉 (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的路径权值之和 （反证法可证）
88
算法描述：
（ 1） 设 A[n][n]为有向网的带权 邻接矩阵,A[i][j]表示弧 (vi,vj )
权值,S为已找到从源点 v0出发的最短路径的终点集合，它的初始状态为 {v0}.辅助数组 dist[n]为各终点当前找到的最短路径的长度，
它的初始值为 dist[i]＝ A[v0,i] //即邻接矩阵中第 v0行的权值
（ 2） 选择 u，使得
dist[u]＝ min{dist[w]|w∈V -S } //w是 S集之外的顶点
//dist[u]是从源点 v0到 S集外所有顶点的弧中最短的一条
S=S∪{u} //将 u加入 S集
（ 3） 对于所有不在 S中的终点 w，若
dist[u]+ A[u,w]< dist[w] //即 (v0,u)＋ (u,w)<(v0,w)
则修改 dist[w]为,dist[w]＝ dist[u]+ A[u,w]
（ 4） 重复操作 (2),(3)共 n-1次，由此求得从 v0到各终点的最短路径。
89
20 0 10 30 max max max
Dist[7]
▲
20 0 10 30 15 max max
Dist[7]
▲
Path[7][7]
S={b}
(a) Dist和 Path的初始状态，
从中求得从 b到 c的最短路径
b a
cb
b d
Path[7][7]
S={b,c}
(a) 修改 Dist和 Path的值，
从中求得从 b到 e的最短路径
b a
cb
b d
cb e
单元最短路径算法执行过程示例
90
20 0 10 27 15 max 30
Dist[7]
▲
20 0 10 27 15 max 29
Dist[7]
▲
Path[7][7]
S={b,c,e}
(a) Dist和 Path的初始状态，
从中求得从 b到 a的最短路径
b a
cb
Path[7][7]
S={b,c,e,a}
(a) 修改 Dist和 Path的值，
从中求得从 b到 d的最短路径
b a
cb
b c
cb e
单元最短路径算法执行过程示例
ab g
e db c e d
cb e
b c e g
91
20 0 10 27 15 max 29
Dist[7]
▲
20 0 10 27 15 max 29
Dist[7]
▲
Path[7][7]
S={b,c,e,a,d}
(a) Dist和 Path的初始状态，
从中求得从 b到 g的最短路径
b a
cb
Path[7][7]
S={b,c,e,a,d,g}
(a) 修改 Dist和 Path的值，
可见从 b到 f没有路径
b a
cb
b c
cb e
单元最短路径算法执行过程示例
ab g
e db c e d
cb e
b c e g
92
终点 从 v0到各终点的 dist值和最短路径
v1
v2
v3
v4
v5
vj
60
{v0,v2,v3}
50
{v0,v4,v3}
30
{v0,v4}
90
{v0,v4,v5}
60
{v0,v4,v3,v5}
5
5
40
3
1 2
100 60
30
10
10 20
50
s {v0,v2} {v0,v2,v4} {v0,v2,v4,v3} {v0,v2,v4,v3,v5}
10
{v0,v2}
∞
30
{v0,v4}
100
{v0,v5}
∞ ∞ ∞ ∞
例：
v2 v4 v3 v5
100
{v0,v5}0
1
2
3
4
5
dist[w]
0 1 2 3 4 5
与最小生成树的不同点：路径可能是累加的！
10
{v0,v2}
50
{v0,v4,v3}
30
{v0,v4}
(v0,v2)+ (v2,v3)<(v0,v3)S之外的当前最短路径之顶点
93
① AOV网 (Activity On Vertices)—用 顶点 表示活动的网络
AOV网定义,若用有向图表示一个工程，在图中 用顶点表示活动，用弧表示活动间的优先关系。 Vi 必须先于活动 Vj 进行。 则这样的有向图叫做用顶点表示活动的网络，简称 AOV。
② AOE网 (Activity On Edges)—用 边 表示活动的网络
AOE网定义,如果在无环的带权有向图中,用 有向边表示一个工程中的活动，
用边上权值表示活动持续时间，用顶点表示事件,则这样的有向图叫做用边表示活动的网络，简称 AOE。
二、两种常用的活动网络 (Activity Network):
一、何为有向无环图（ DAG 图 ）
实例
L
B
E F G
F G
有向树
B
E F G
L F G
DAG图
B
E F G
L F G
有向图 (含环 )
A B
A B10
AOV网络的用途,我们经常用有向图来描述一个工程或系统的进行过程。一般来说，一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成。
AOV网络若用于教学计划的制定，可以解决哪些课程是必须先修的，哪些课程是可以并行学习的。
7.6 拓扑排序
94
对有向图进行如下操作,
按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。
例如,对于下列有向图
B
DA
C可求得 拓扑有序序列,A B C D 或 A C B D
由此所得顶点的线性序列称之为 拓扑有序序列
B
DA
C
反之，对于下列有向图不能求得它的拓扑有序序列。
因为图中存在一个回路 {B,C,D}
三、什么叫拓扑排序？
对一个有向无环图中的顶点排成一个具有前后次序的线性序列。
7.6 拓扑排序
95
四、如 何进行拓扑排序？
1）从有向图中选取一个没有前驱的顶点，并输出之 ;
重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。
2）从有向图中删去此顶点以及所有以它为尾的弧 ;
在算法中需要用定量的描述替代定性的概念没有前驱的顶点入度为零的顶点删除顶点及以它为尾的弧弧头顶点的入度减 1
a
b
c
g
h
d
f
e
a b h c d g f e
7.6 拓扑排序
96
进行拓扑排序的方法：
1,输入 AOV网络。令 n 为顶点个数。
2,在 AOV网络中 选一个没有直接前驱的顶点,并输出之 ;
3,从图中删去该顶点,同时删去所有它发出的有向边 ;
4,重复以上 2,3 步,直到：
全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；
或：
图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时 AOV网络中必定存在有向环。
拓扑排序算法,重复选择没有直接前驱的顶点。
97
取入度为零的顶点 v;
while (v<>0) {
printf(v); ++m;
w=FirstAdj(v);
while (w<>0) {
inDegree[w]--;
w:=nextAdj(v,w);
}
取下一个入度为零的顶点 v;
}
if (m<n) printf(―图中有回路” );
算法描述
98
为避免每次都要搜索入度为零的顶点，在算法中设置一个,栈”,
以保存,入度为零” 的 顶点 。
CountInDegree(G,indegree); //对各顶点求入度
InitStack(S);
for ( i=0; i<G.vexnum; ++i)
if (!indegree[i]) Push(S,i); //入度为零的顶点入栈
count=0; //对输出顶点计数
while (!EmptyStack(S)) {
Pop(S,v); ++count; printf(v);
for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){
--indegree(w); // 弧头顶点的入度减一
if (!indegree[w]) Push(S,w); //新产生的入度为零的顶点入栈
}
}
if (count<G.vexnum) printf(―图中有回路” )
99
例课程代号 课程名称 先修棵
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--C7--C9--C10--C11--C6--C12--C8
或,C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8
一个 AOV网的拓扑序列不是唯一的六,拓扑排序举例
100
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
C7
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5
(5)
101
C6
C8
C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
(7)
C6
C8
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10
（ 8）
C6
C8
C9 C10
C11
C12
拓扑序列,C1--C2--C3--C4--C5--C7
(6)
C6
C8C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11
(9)
C8C12
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6
(10)
C8
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6--C12
(11)
（ 11）
拓扑序列,C1--C2--C3--C4--C5--C7--C9
--C10--C11--C6--C12--C8
(12)
102
7.7 关键路径问题,假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。
问,哪些子工程项是“关键工程”？
即,哪些子工程项将影响整个工程的完成期限的。
构造关键路径的方法,要用到拓扑排序和逆拓扑排序
在 AOE网络中,有些活动 顺序进行,有些活动 并行进行 。
从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。
这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。
完成整个工程所需的时间取决于从源点到汇点的最长路径长度，
即在这条路径上所有活动的持续时间之和。 这条路径长度最长的路径就叫做关键路径 (Critical Path)。
103
AOE网络的用途,常用于大型工程的计划管理。 利用 AOE网络可以解决以下两个问题：
(1) 完成整个工程至少需要多少时间。
(假设网络中没有环 )?
(2) 为缩短完成工程所需的时间,应当加快哪些活动?
或者说，哪些活动是影响工程进度的关键？
AOV网定义,若用有向图表示一个工程，在图中 用顶点表示活动，用弧表示活动间的优先关系。 Vi 必须先于活动 Vj 进行。 则这样的有向图叫做用顶点表示活动的网络，
简称 AOV。
104
整个工程完成的时间为,从有向图的 源点 到 汇点的最长路径。
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
7
2
4
4
例如,
关键活动,该弧上的 权值增加 将使有向图上的 最长路径的长度增加。
源点汇点该活动的 最早 开始时间 = 该活动 的 最迟 开始时间
105
假设第 i条弧为 <j,k>,则 对第 i项活动言
“活动 (弧 )‖的最早开始时间 ee(i),ee(i) = ve(j);
―活动 (弧 )‖的最迟开始时间 el(i),el(i) = vl(k)–dut(<j,k>);
事件发生时间的计算公式,
ve(源点 ) = 0; ve(k) = Max{ve(j) + dut(<j,k>)}
vl(汇点 ) = ve(汇点 ); vl(j) = Min{vl(k) – dut(<j,k>)}
事件 (顶点 )的最早发生时间 ve(j):从源点到顶点 j的最长路径长度 ;
事件 (顶点 )的最迟发生时间 vl(k):从顶点 k到汇点的最短路径长度 ;
算法的实现要点,显然,求 ve的顺序应该是按拓扑有序的次序 ; 而求
vl的顺序应该是按拓扑逆序的次序 ; 因为拓扑逆序序列即为拓扑有序序列的逆序列，因此应该在拓扑排序的过程中，另设一个,栈”
记下拓扑有序序列。
Ve(j) 的求法：
V1 VJ
3
5
12
88
Ve(Vj) = 3,5,12,88的最大值 88
起点,
0
V1 VJ
Ve(Vj) = Vj 的起始结点的最早发生时间
+ 各自的边的权值中的和的最大值 88
Vu
Vv
Vw
Vx
2
3
9
82
1
2
3
6
由源点至收点 注意,本图说明由已知的所有的起始结点的 Ve,可得知终止结点的 Ve 。
如：从 Ve(Vu),Ve (Vv),Ve (Vw),Ve
(Vx) 可知 Ve(Vj)
注意,开始时只有源点的 Ve ＝ 0 已知，利用拓扑排序的序列可得到每一个结点的 Ve 。 且结点的 Ve 确定次序和 拓扑排序的序列相同。
关键路径
Vl(j)） 的求法：
Vj Vn
Vl(Vj) = 取 10-2,10-4,10-3,10-7的最小值 3
2
4
3
7
10
10
收点
Vj Vn
Vl(Vj) = 取终止结点的最迟发生时间
- 各自的边的权值的差的最小值 3
10
10
收点
Vu
Vv
Vw
Vx
8
8
5
1
2
1
2
9 由收点至源点注意,本图说明由已知的所有的终止结点的 Vl,可得知起始结点的 Vl 。
如：从 Vl(Vu),Vl (Vv),Vl (Vw),Vl (Vx)
可知 Vl(Vj)
注意,开始时只有收点的 Vl ＝ Ve(Vn) 已知，利用逆拓扑排序的序列可得到每一个结点的 Vl 。 且结点的 Vl 确定次序和逆 拓扑排序的序列相同。
关键路径
108
a
b
c
d
e
f
g
h
k
6
4
5
2
1
1
8
7
2
4
4
a b c d e f g h k
ve
vl
0 0 0 0 0 0 0 0 06 4 5 7 1157 15 14 18
181818181818181818 16 1486 6 1080 7
拓扑有序序列,a - d - f - c - b - e - h - g - k
109
0 6 4 5 7 7 15 14 18
1814161078660
0 0 0 6 4 5 7 7 7 15 14
14160 2 3 6 6 8 8 7 10
ab ac ad be ce df eg eh fh gk hk
权 6 4 5 1 1 2 8 7 4 2 4
e
l
a b c d e f g h k
ve
vl
110
算法描述
输入顶点和弧信息，建立其邻接表
计算每个顶点的入度
对其进行拓扑排序
–排序过程中求顶点的 Ve[i]
–将得到的拓扑序列进栈
按逆拓扑序列求顶点的 Vl[i]
计算每条弧的 e[i]和 l[i],找出 e[i]=l[i]的关键活动
9
8
7
64
5
3
2
1
a6=2
例 设一个工程有 11项活动,9个事件事件 V1——表示整个工程开始事件 V9——表示整个工程结束
(1) 完成整项工程至少需要多少时间？
(2) 哪些活动是影响工程进度的关键？
111
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
^
112
求关键路径步骤
求 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
113
图存储结构遍 历邻接矩阵邻 接 表十字链表邻接多重表深度优先搜索 DFS
广度优先搜索 DFS
无向图的应用应用图的连通分量图的生成树 最小生成树 Prim算法
Kruskal算法有向 (无环 )图的应用最短路径 Dijkstra算法
Floyd算法
（利用 DFS）
本章小结
(利用 DFS和 BFS)
114
7.8 广义表（ Lists）
① 元素的值并非原子类型，可以再分解，表中元素也是一个线性表（即广义的线性表）。
② 所有数据元素仍 属同一数据类型 。
广义表的定义广义表的存储结构广义表的遍历广义表的特点,一种特殊的线性表
115
7.8.1 广义表的定义广义表是线性表的推广，也称为列表（ lists）
记为,LS = ( a1,a2,……,an )
广义表名 表头 (Head） 表尾 (Tail)
1、定义：
① 第一个 元素是表头,而其余元素组成的 表称为表尾；
② 用小写字母表示原子类型，用 大写字母 表示列表。
n是表长在广义表中约定：
讨论,广义表与线性表的区别和联系？
广义表中元素既可以是原子类型，也可以是列表；
当每个元素都为原子且类型相同时，就是线性表。
116
广义表是 递归 定义的线性结构，
LS = (?1,?2,,?n )
其中,?i 或为原子 或为广义表例如,A = ( )
F = (d,(e))
D = ((a,(b,c)),F)
C = (A,D,F)
B = (a,B) = (a,(a,(a,,) ) )
117
广义表 LS = (?1,?2,…,?n )的结构特点,
1) 广义表中的数据元素有相对 次序 ;
2) 广义表的 长度 定义为最外层包含元素个数 ;
3) 广义表的 深度 定义为所含括弧的重数 ;
注意,“原子”的深度为 0 ;
“空表”的深度为 1 。
4) 广义表可以 共享 ;
5) 广义表可以是一个 递归 的表 ;
递归表的深度是无穷值，长度是有限值。
118
6) 任何一个非空广义表 LS = (?1,?2,…,?n)
均可分解为表头 Head(LS) =?1 和表尾 Tail(LS) = (?2,…,?n) 两部分例如,D = ( E,F ) = ((a,(b,c)),F )
Head( D ) = E Tail( D ) = ( F )
Head( E ) = a Tail( E ) = ( ( b,c) )
Head( (( b,c)) ) = ( b,c) Tail( (( b,c)) ) = ( )
Head( ( b,c) ) = b Tail( ( b,c) ) = ( c )
Head( ( c ) ) = c Tail( ( c ) ) = ( )
119
E=(a,E)=(a,(a,E))= (a,(a,(a,…….))),E为递归表
1） A =( )
2） B = ( e )
3） C =( a,( b,c,d ) )
4） D=( A,B,C )
5） E=(a,E)
例,求下列广义表的长度。
n=0,因为 A是空表
n=1，表中元素 e是原子
n=2,a 为原子,(b,c,d)为子表
n=3,3个元素都是子表
n=2,a 为原子,E为子表
D=(A,B,C)=(( ),(e),(a,(b,c,d))),共享表
120
A B
D
C
e
a
b c d
② A=( a,(b,A) )
例,试用图形表示下列广义表,
（设 代表原子,代表子表）e
① D=(A,B,C)=( ( ),(e),( a,(b,c,d) ) )
A
a
b
① 的长度为 3，深度为 3 ② 的长度为 2，深度为 ∞
深度＝括号的重数＝ 结点的层数
121
广义表是一个 多层次 的 线性结构例如：
D=(E,F)
其中,
E=(a,(b,c))
F=(d,(e))
D
E F
a ( ) d ( )
b c e
122
7.8.2 广义表的存储结构由于广义表的元素可以是不同结构（原子或列表），难以用顺序存储结构表示,通常用链式结构,每个 元素 用一个结点表示。
1.原子结点,表示原子，可设 2个域或 3个域，依习惯而选。
valuetag=0
标志域 数值域注意：列表的,元素,还可以是列表，所以结点可能有两种形式
tpatomtag=０
标志域 值域 表尾指针法 2：标志域、值域、表尾指针指向下一结点法 1：标志域，数值域
123
tphptag=1
标志域 表头指针 表尾指针
2.表结点,表示列表，若表不空，则可分解为表头和表尾，用
3个域表示,标志域，表头指针，表尾指针。
① A =( )
^1
0 e
③ C =( a,( b,c,d ) )
1 ^1
1
0 b 0 d
1 ^1
例：
② B=( e )
0 a
A=NULL
指向子表 指向下一结点
^^1
0 c
124
⑤ E=(a,E)
④ D=( A,B,C )＝ (( ),(e),(a,(b,c,d)))
0 a
^1
1
^1
1 ^1
1 ^1
10 e 0 a 1 ^1
^1
0 b 0 d0 c
125
1) 表头、表尾分析法,
构造存储结构的两种分析方法,
若表头为原子，则为空表 ls = NIL
非空表 ls tag=1
指向表头的指针指向表尾的指针
tag=0 data
否则，依次类推。
126
L = ( a,( x,y ),( ( x ) ) )a ( x,y ) ( )
1L
= ( )
0 a
1 1
1 1
1
0 x
( )x
127
1 1 1 ls …?
2) 子表分析法,
若子表为原子，则为空表 ls=NIL
非空表指向子表 1
的指针
tag=0 data
否则，依次类推。
指向子表 2
的指针指向子表 n
的指针
128
例如,
ls
((x))
LS=( a,(x,y),((x)) )
a (x,y)
129
广义表从结构上可以分解成广义表 = 表头 + 表尾或者广义表 = 子表 1 + 子表 2 + ··· + 子表 n
因此常利用分治法求解之。
算法设计中的关键问题是,如何将 l
个子问题的解组合成原问题的解。
130
广义表的头尾链表存储表示
typedef enum {ATOM,LIST} ElemTag;
//ATOM==0:原子,LIST==1:子表
typedef struct GLNode {
ElemTag tag; //标志域
union{
AtomType atom; //原子结点的数据域
struct {struct GLNode *hp,*tp;} ptr;
};
} *GList tag=1 hp tpptr表结点
tag=0 data
131
7.8.3 广义表的遍历广义表由遍历分为表头和表尾两部分。
可以直接求解的两种简单情况为,
空表 ;
原子结点可以直接访问。
将广义表分解成表头和表尾两部分，分别
(递归 )遍历求得广义表的每个结点。
132
若 ls= NIL 则 输出（）
若 ls= 原子 则 输出该原子否则输出（,
遍历 表头 ls->ptr.hp
遍历 表尾 ls->ptr.tp
输出 ）；
遍历广义表的算法描述如下,
133
void OutputGList( Glist LS ) {
if (!LS) cout << ―()‖;
else {
if ( LS->tag==ATOM ) cout << LS->data;
else {
cout << ―(―;
p = LS;
while ( p ) {
OutputGList( p->ptr,hp );
p = p->ptr.tp;
if ( p ) cout << ―,‖;
} // while
cout << ―)‖;
}
}
}
134
1,熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。
2,熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、
深度优先搜索和广度优先搜索的算法。应注意图的遍历算法与树的遍历算法之间的类似和差异。
3,应用图的遍历算法求解各种简单路径问题。
4,理解教科书中讨论的各种图的算法。
小结图是一种复杂的非线性结构。本章介绍了图的基本概念，
图的相邻矩阵和邻接表两种常用的存储表示方法，讨论了图的周游,最小生成树、最短路径、拓扑排序及关键路径等问题，并给出了相应的算法。重点是掌握图的存储表示和各种算法的基本思想。
