图论深度优先搜索

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


关于图遍历

图遍历即图的遍历,指从图中任一顶点出发,对图中的所有顶点访问一次。图的遍历与树的遍历相似,但图的结构更加复杂,比如要考虑回路的情况。图的遍历操作是一种基本操作,很多其他操作都建立在图遍历基础之上。图的遍历算法主要有广度优先搜索和深度优先搜索,这里看深度优先搜索。

深度优先搜索

深度优先搜索(Depth First Search),简称DFS。简单来说,深度优先搜索就是对每一个可能的分支深入到不能在深入为止,且每个顶点只能访问一次。DFS的时间复杂度为$O(|V|+|E|)$,其中$|V|$为图的顶点数,$|E|$为图的边数。

核心思想

  1. 选择一个初始顶点,并将其标记为已访问;
  2. 若当前顶点存在未被访问过的邻接顶点,则任选一个顶点作为下一个顶点,并将下一个顶点标记为已访问;
  3. 若当前顶点的所有邻接顶点都已被访问过,则回退到最近一次访问的顶点;
  4. 不断执行步骤2和步骤3,直到与起始顶点相通的全部顶点都访问完毕;
  5. 如果图中的顶点还有未被访问的,则再选出其中一个顶点作为起始顶点,继续执行步骤2到步骤4;
  6. 遍历结束。

搜索过程

在实现深度优先搜索的过程中需要用到一个栈和一个数组,栈用于保存所有待检测的顶点,而数组用于标识哪些顶点已被访问,F表示未被访问,T表示已被访问。

对于一个拥有8个顶点的无向加权图,分别用0-7来表示图的每个顶点,因为遍历与边的权重无关,这里将权重值省略。

image

选择3作为初始顶点,将其推入栈中,栈顶的元素即是当前检测的顶点,并将数组对应元素标为T。

image

从顶点3开始,选择一条边进行检测,选择到达顶点1的边,

image

因为顶点1的访问标记为F,说明还未被访问过,于是将1推入BFS栈中,同时将访问标记改为T。

image

此时栈顶元素为1,继续从顶点1选择一条边进行检测,选择到达顶点0的边,

image

因为顶点0的访问标记为F,说明还未被访问过,于是将0推入BFS栈中,同时将访问标记改为T。

image

此时栈顶的元素为0,继续从顶点0选择一条边进行检测,选择到达顶点1的边,因为访问标记为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

继续从顶点0选择一条边进行检测,选择到达顶点2的边,

image

因为顶点2的访问标记为F,说明还未被访问过,于是将2推入BFS栈中,同时将访问标记改为T。

image

此时栈顶的元素为2,继续从顶点2选择一条边进行检测,选择到达顶点0的边,因为访问标记为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

继续从顶点2选择一条边进行检测,选择到达顶点1的边,因为访问标记为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

此时顶点2的所有边都已经检查完,已经无法继续深入,所以对顶点2进行出栈操作。然后栈顶元素为0,

image

对于顶点0,顶点2和顶点1的边之前都已经检测过了,已经不存在未访问的边,所以直接对顶点0进行出栈操作。然后栈顶元素为1,

image

继续从顶点1选择一条未访问的边进行检测,前面检测顶点1时我们是选择了往顶点0的边,所以还剩下顶点2和顶点3未访问过,分别对它们进行检测,发现访问标记都为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

image

此时顶点1的所有边都已经检查完,对顶点1进行出栈操作。然后栈顶元素为3,

image

继续从顶点3选择一条未访问的边进行检测,前面检测顶点3时我们是选择了往顶点1的边,所以还剩下顶点4和顶点5未访问过,这次选择顶点4的边。

image

因为顶点4的访问标记为F,说明还未被访问过,于是将4推入BFS栈中,同时将访问标记改为T。

image

此时栈顶元素为4,从顶点4选择一条边进行检测,选择到达顶点3的边,因为访问标记为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

继续从顶点4选择一条边进行检测,选择到达顶点6的边,

image

因为顶点6的访问标记为F,说明还未被访问过,于是将6推入BFS栈中,同时将访问标记改为T。

image

此时栈顶元素为6,从顶点6选择一条边进行检测,选择到达顶点4的边,因为访问标记为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

继续从顶点6选择一条边进行检测,选择到达顶点5的边,

image

因为顶点5的访问标记为F,说明还未被访问过,于是将5推入BFS栈中,同时将访问标记改为T。

image

此时栈顶元素为5,分别检测顶点5到顶点3和顶点6的边,发现顶点访问标记都为T,无法继续深入,所以对5进行出栈操作,

image

此时栈顶元素为6,顶点6没有未访问过的边,所以对6进行出栈操作,

image

此时栈顶元素为4,顶点4到顶点7的边还未被访问过,对其进行访问,

image

因为顶点7的访问标记为F,说明还未被访问过,于是将7推入BFS栈中,同时将访问标记改为T。

image

顶点7发现没办法继续深入访问,于是对7进行出栈操作。

image

此时栈顶元素为4,顶点4没有未访问过的边,所以对4进行出栈操作,

image

此时栈顶元素为3,前面处理顶点3时我们已经检测了顶点1和顶点4的边,所以这次选择顶点5的边。顶点5的访问标记为T,说明已经被访问过,所以访问标记和DFS栈都不更新。

image

接着发现顶点3所有边都已经检测完毕,所以对3进行出栈操作。现在DFS栈内没有任何元素,所以我们已经完成了整个遍历过程。

image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 图论深度优先搜索
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏