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