logo图片
数据结构与算法

深度优先遍历

深度优先搜索 (DFS) 算法以深度运动遍历图,并使用堆栈记住在任何迭代中出现死路时获取下一个顶点以开始搜索。
深度优先遍历
如上例所示,DFS 算法首先从 S 到 A 到 D 到 G 到 E 到 B,然后到 F,最后到 C。它采用以下规则。
Rule 1-访问相邻的未访问顶点。将其标记为已访问。显示它。将其推入堆栈。 Rule 2-如果没有找到相邻的顶点,则从堆栈中弹出一个顶点。 (它会从栈中弹出所有没有相邻顶点的顶点。) 规则 3-重复规则 1 和规则 2,直到堆栈为空。
步骤 遍历 描述
1 深度优先搜索第一步 初始化堆栈。
2 深度优先搜索第二步 S标记为已访问并将其放入堆栈。从 S 探索任何未访问的相邻节点。我们有三个节点,我们可以选择其中任何一个。对于本例,我们将按字母顺序获取节点。
3 深度优先搜索第三步 A标记为已访问并将其放入堆栈。从 A 探索任何未访问的相邻节点。SD 都与 A 相邻,但我们只关注未访问的节点。
4 深度优先搜索第四步 访问D并将其标记为已访问并放入堆栈。在这里,我们有 BC 节点,它们与 D 相邻并且都未被访问。但是,我们将再次按字母顺序选择。
5 深度优先搜索第五步 我们选择B,标记为已访问并入栈。这里 B 没有任何未访问的相邻节点。因此,我们从堆栈中弹出 B
6 深度优先搜索第六步 我们检查栈顶是否返回前一个节点,并检查是否有未访问的节点。在这里,我们发现 D 位于栈顶。
7 深度优先搜索第七步 现在只有未访问的相邻节点来自 DC。所以我们访问C,将其标记为已访问并入栈。
由于 C 没有任何未访问的相邻节点,因此我们不断弹出堆栈,直到找到具有未访问的相邻节点的节点。在这种情况下,没有,我们会一直弹出直到堆栈为空。
昵称: 邮箱:
Copyright © 2020 立地货 All Rights Reserved.
备案号:京ICP备14037608号-4