1
7.1 基本术语
7.2 存储结构
7.3 图的遍历
7.4 图的连通性
7.5 图的应用
第7章 图
2
7.3 图的遍历
遍历:从已给的连通图中某一顶点出发,沿着一些边,
访遍图中所有的顶点,且使每个顶点仅被访问一次,
就叫做图的遍历,它是图的基本运算。
遍历实质:找每个顶点的邻接点的过程。
图的特点:图中可能存在回路,且图的任一顶点都可能与
其它顶点相通,在访问完某个顶点之后可能会沿着某
些边又回到了曾经访问过的顶点。
解决思路:可设置一个辅助数组 visited [n ],用来标
记每个被访问过的顶点。它的初始状态为false,
在图的遍历过程中,一旦某一个顶点i被访问,就
立即改 visited [i]为true,防止它被重复访问。
怎样避免重复访问?
3
深度优先搜索和广度优先搜索图常用的遍历:
一、深度优先搜索( DFS ) Depth_First Search
基本思想:——类似于树的先根遍历过程。
1、连通图的深度优先搜索遍历
步骤:
• 访问起始点 v;
• 依次从v的未被访问的邻接点出发深度优先遍历
图直至图中所有和v有路径相通的顶点都被访问
到。
4
v1
v1
v2 v3
v8
v7v6v4 v5
DFS 结果:例1:
→ → → →
→ → →
v2 v4 v8
v5 v3 v6 v7
起点
应退回到V8,因为
V2已有标记
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
5
对于无向图,这个算法可以遍历到v顶点所在的连通
分量中的所有顶点,而与v顶点不在一个连通分量中的
所有顶点遍历不到;
对于有向图可以遍历到起始顶点v能够到达的所有顶
点。
若希望遍历到图中的所有顶点,就需要在上述深度
优先遍历算法的基础上,增加对每个顶点访问状态的
。
2、非连通图的深度优先搜索遍历
步骤:
• 访问起始点 v及图中所有和v有路径相通的顶点。
• 如果图中尚有顶点未被访问,则以该顶点为起始点,
进行深度优先搜索遍历。重复上述过程,直至所有
顶点都已被访问。
6
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
a
c
h k
fed
b
g
访问标志:
访问次序:
例2:
0 1 2 3 4 5 6 7 8
8
1
2 3 4 5
6
7
0
7
void DFSTraverse(Graph G,
Status (*Visit)(int v)) {
// 对图 G 作深度优先遍历。
VisitFunc = Visit;
for (v=0; v
表示图,遍历图中每一个
顶点都要从头扫描该顶点所在行,因此遍历全部
顶点所需的时间为O(n2)。
(2)如果用邻接表来表示图,虽然有 2e 个表结点,
但只需扫描 e 个结点即可完成遍历,加上访问 n
个头结点的时间,因此遍历图的时间复杂度为
O(n+e)。
结 论:
稠密图适于在邻接矩阵上进行深度优先遍历;
稀疏图适于在邻接表上进行深度优先遍历。
9
二、广度优先搜索( BFS )
基本思想:——仿树的层次遍历过程。
Breadth_First Search
• 在访问了起始点v之后,依次访问 v的各个未曾访问
过的邻接点;
• 然后按这些顶点被访问的先后次序依次访问它们的
邻接点,直至图中所有和V有路径相通的顶点都被访
问到。
• 若此时图中尚有顶点未被访问,则另选图中一个未曾
被访问的顶点作起始点,重复上述过程,直至图中
所有顶点都被访问到为止。
步骤:
10
v1
v1
v2 v3
v8
v7v6v4 v5
BFS 结果:
例1:
→ →
→
→v2 v3
→v4 v5 →v6 v7→v8
v3 →
BFS 结果:
→ v4→ v5 →
起点
起点
v2 → v1 → v6
v9 → v8 → v7
例2:
11
讨论:
答:利用一个队列结构
顶点访问顺序,将访问的
每个顶点入队,然后,再依次出队,出队时访问其邻
接点并将邻接点入队。
(2)如何避免重复访问某个顶点?
(1)在广度优先遍历中,要求先被访问的顶点其邻接点
也被优先访问,应采用何种方式记录顶点访问顺序?
答:创建一个一维数组visited[0..n-1](n是图中顶
点的数目),用来记录每个顶点是否已经被访问过。
(3)广度优先搜索有回退的情况吗?
12
答:广度优先搜索是一种分层的搜索过程,每向前走
一步可能访问一批顶点,不像深度优先搜索那样有回
退的情况。因此广度优先搜索不是一个递归的过程,
其算法也不是递归的。
void BFSTraverse(Graph G, Status (*Visit)(int v)){
for (v=0; v
方法 :设置一个辅助数组,对当前V-U集中的每
个顶点,记录和顶点集U中顶点相连接的代价最小
的边。对每个属于V-U的顶点vi,在辅助数组中存
在一个相应的分量closedge[i-1],它包含两个域,
其中lowcost存储该边上的权。显然,
closedge[i-1].lowcost=Min{cost(u,vi)|u€U}
存储方式:
struct {
VertexType adjvex; // U集中的顶点序号
VRType lowcost; // 边的权值
} closedge[MAX_VERTEX_NUM];
24
closedge
0 1 2 3 4 5 6
Adjvex
Lowcost
a b
c
d
e
g
f
19 5
14
18
27
16 8
21
3
a
e
12
d
c
b
7
a a a
19 14 1814
例如:
e
12
e e
8 168
d
3
d d
7 213
c
55
∞ 19 ∞ ∞ 14 ∞ 18
19 ∞ 5 7 12 ∞ ∞
∞ 5 ∞ 3 ∞ ∞ ∞
∞ 7 3 ∞ 8 21 ∞
14 12 ∞ 8 ∞ ∞ 16
∞ ∞ ∞ 21 ∞ ∞ 27
18 ∞ ∞ ∞ 16 27 ∞
(a b c d e f g)
Prim算法的时间效率=O(n2)
(a b c d e f g)
25
具体做法: 先构造一个只含 n 个顶点的子图 SG,然后从
权值最小的边开始,若它的添加不使SG 中产生回路,
则在 SG 上加上这条边,如此重复,直至加上 n-1 条边
为止。
考虑问题的出发点: 为使生成树上边的权值之和达到
最小,则应使生成树中每一条边的权值尽可能地小。
克鲁斯卡尔算法的基本思想:
1
4
65
2 3
1
56
55
463
6
2
15
43 2
1
3
5
2 4
6
Kruskal算法的时间效率=O(elog2e)
第7章 图
7.3 图的遍历
一、深度优先搜索( DFS )
幻灯片编号 4
幻灯片编号 5
幻灯片编号 6
幻灯片编号 7
DFS 算法效率分析:
二、广度优先搜索( BFS )
幻灯片编号 10
幻灯片编号 11
幻灯片编号 12
幻灯片编号 13
BFS 算法效率分析:
幻灯片编号 15
例1 :画出下图的生成树。
例2:画出下图的生成森林(或极小连通子图)
幻灯片编号 18
幻灯片编号 19
2. 求无向网的最小生成树
幻灯片编号 21
幻灯片编号 22
幻灯片编号 23
幻灯片编号 24
幻灯片编号 25