没有合适的资源?快使用搜索试试~ 我知道了~
数据结构第7章 图3PPT课件.pptx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 194 浏览量
2021-10-08
07:37:41
上传
评论
收藏 708KB PPTX 举报
温馨提示
试读
60页
数据结构第7章 图3PPT课件.pptx
资源推荐
资源详情
资源评论
7.3 图的遍历
图的遍历:从图中某个顶点出发游历图,访遍图中其
余顶点,并且使图中的每个顶点仅被访问一次的过程。
在图中,访问部分顶点后,可能又沿着其他边回到已
被访问过的顶点。为保证每一个顶点只被访问一次,必
须对顶点进行标记,一般用一个辅助数组 visit[0..n-1]
作为对顶点的标记,当顶点 v
i
未被访问, visit[i] 值为
0 ;当 v
i
已被访问,则 visit[i] 值为 1 。
通常,有两种遍历图的路径:深度优先搜索和广度优
先搜索,对无向图和有向图都适用。
第 1 页 / 共 60 页
图的两种遍历方法:
1. 深度优先搜索
图的深度优先遍历类似于树的先根遍历。
采用的搜索方法的特点是尽可能先对纵深方向进
行搜索。这种搜索方法称为深度优先搜索 (Depth-
First Search) 。相应地,用此方法遍历图就称之
为图的深度优先遍历。
2. 广度优先搜索
广度优先遍历类似于树的按层次遍历。
采用的搜索方法的特点是尽可能先对横向进行搜
索,故称其为广度优先搜索 (Breadth-
FirstSearch) 。相应的遍历就称为广度优先遍历。
第 2 页 / 共 60 页
1. 深度优先搜索 DFS
基本思想:
选择图中某个 ( 强 ) 连通分量中某个顶点 v 出发:
⑴ 访问顶点 v ,并将其访问标记置为访问过,即
visited[v] = 1 ;
⑵ 依次从 v 的未被访问的邻接点出发,继续对图进
行深度优先遍历,直到 ( 强 ) 连通分量中和 v 有路
径相通的顶点都被访问过;
⑶ 如果图中还有顶点未被访问,则另选图中其余
( 强 ) 连通分量中一个未被访问的顶点作起点,重复
上述过程,直至图中所有顶点都被访问过为止。
第 3 页 / 共 60 页
非连通图的每一个连通部分称为连通分量。
连通分量:
连通:
在无向图中,如果从顶点 v 到顶点 w 有路径,
则称 v 和 w 是连通的。
L
A
B
M
C
F
I
D
G
J
E
H
K
D E
I
G H
K
L
A
B
M
C
F
J
第 4 页 / 共 60 页
( 强 ) 连通分量的遍历:
W1 、 W2 和 W3 均为 V
的邻接点。
SG1 为从 W1 出发可以访
问到的顶点集;
SG2 为从 W2 出发可以访问到的顶点集;
SG3 为从 W3 出发可以访问到的顶点集。
访问顺序: SG1 SG2 SG3 。
交集部分只访问一次。
第 5 页 / 共 60 页
V
W1
W2
W3
SG1
SG2
SG3
剩余59页未读,继续阅读
资源评论
加油学习加油进步
- 粉丝: 1395
- 资源: 52万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功