前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >8-3 图的遍历

8-3 图的遍历

作者头像
TeeyoHuang
发布2019-07-02 10:27:55
4060
发布2019-07-02 10:27:55
举报
文章被收录于专栏:Deep learning进阶路

8-3 图的遍历

和树的遍历类似,图的遍历也是从某个顶点出发,沿着某条搜索路径对图中所有顶点各做一次访问。

若给定的是连通图,则从图中任一顶点出发顺着边可以访问到该图中所有的顶点。

但是有可能在访问了某个顶点之后,可能顺着某条回路又回到了该顶点。

为了避免重复访问同一个顶点,必须记住每个顶点是否被访问过。

为此,可设置一个标志向量 visited [1,...,N],以便说明哪些点被访问过。

常用的遍历方式有两种: 深度优先遍历---DFT,也叫深度优先搜索---DFS 广度优先遍历---BFT,也叫广度优先搜索---BFS。

①深度优先遍历(Depth-First Traverse)

假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点V0为初始出发点(源点),则深度优先遍历可定义如下:

首先访问出发点V0,并将其标记为已访问过;然后依次从V0出发搜索V0的每个邻接点Vj。若Vj未曾访问过,则以Vj为新的出发点继续进行深度优先遍历。

上述搜索方法是递归定义的,它的特点是尽可能先对纵深方向进行搜索,故称之为 深度优先搜索

例如,设x是刚被访问过的点,则下一步选一条从x出发未经检测过的边(x,y),若发现已经 y 被搜索过,则重选另一个未被搜索过的(x,z);如果 y 确实没被访问,那么就又从y出发继续搜索... 知道搜索完从 y 出发的路径,又才回溯到 x 。

②广度优先遍历 (breadth-first traverse)

1、从图中某个顶点V0出发,并访问此顶点;

2、从V0出发,访问V0的各个未曾访问的 邻接点 W1,W2,…,Wk;

然后,依次从 W1, W2, …, Wk 出发访问各自未被访问的邻接点

3、重复步骤2,直到全部顶点都被访问为止。

广度优先遍历在程序上可以用队列来实现。

①首先让一个点V0入队列,然后将其所有 未访问过的邻接点 全部入队列

②然后又将新入队的这些顶点的 未访问过的邻接点,依次入队列

③重复②直至没有剩下顶点。 然后出队列操作即可。

不论采用深度优先搜索遍历, 还是广度优先搜索遍历,如果选定的出发点不同 或者 是 所建立的存储结构不一致,

则可能得到不同的遍历结果。

此外,若一个图是非连通图,则从图中任意一个顶点出发进行深度优先搜索或广度优先搜索,都不能够访问到图中所有的顶点。而只能访问到初始出发点所在的连通分量中的所有顶点。若从每个连通分量中都选一个顶点作为出发点进行搜索,便可访问到整个非连通图中所有的顶点。

因此非连通图的遍历必须多次调用 深度优先搜索 或 广度优先搜索算法。

对于给定的无向图,如何构建它们相对应的生成树或者生成森林?

其实在对无向图进行遍历的时候,遍历过程中所经历过的图中的顶点和边的组合,

就是图的生成树或者生成森林。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年06月25日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 8-3 图的遍历
    • ①深度优先遍历(Depth-First Traverse)
      • ②广度优先遍历 (breadth-first traverse)
      领券
      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档