图的遍历和连通性
1
7.1 基本术语
7.2 存储结构
7.3 图的遍历
7.4 图的连通性
7.5 图的应用
第7章 图
2
7.3 图的遍历
遍历:从已给的连通图中某一顶点出发,沿着一些边,
访遍图中所有的顶点,且使每个顶点仅被访问一次,
就叫做图的遍历,它是图的基本运算。
遍历实质:找每个顶点的邻接点的过程。
图的特点:图中可能存在回路,且图的任一顶点都可能与
其它顶点相通,在访问完某个顶点之后可能会沿着某
些边又回到了曾经访问过的顶点。
解决思路:可设置一个辅助数组 visited [n ],用来标
记每个被访问过...
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
记录顶点访问顺序,将访问的
每个顶点入队,然后,再依次出队,出队时访问其邻
接点并将邻接点入队。
(2)如何避免重复访问某个顶点?
(1)在广度优先遍历中,要求先被访问的顶点其邻接点
也被优先访问,应采用何种方式记录顶点访问顺序?
答:创建一个一维数组visited[0..n-1](n是图中顶
点的数目),用来记录每个顶点是否已经被访问过。
(3)广度优先搜索有回退的情况吗?
12
答:广度优先搜索是一种分层的搜索过程,每向前走
一步可能访问一批顶点,不像深度优先搜索那样有回
退的情况。因此广度优先搜索不是一个递归的过程,
其算法也不是递归的。
void BFSTraverse(Graph G, Status (*Visit)(int v)){
for (v=0; v
本文档为【图的遍历和连通性】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。