数据结构中的 DFS（深度优先遍历）：什么是、排序和应用

DFS在数据结构中的意义

数据结构中的 DFS，也称为深度优先遍历，是一种递归算法，主要用于搜索图或树数据结构的所有顶点。 遍历是对图的每个节点的访问。 该算法从根节点（可能是图中的根节点的任意节点）开始，并在回溯之前沿着每个分支尽可能远。

这个想法是从根节点或任意节点开始并保持节点标记。 在此之后，您需要移动到未标记的相邻节点并继续此循环，直到没有未标记的相邻节点。 然后回溯并检查未标记的其他节点并遍历它们。 最后一步是打印路径中的节点。

算法

制定一个递归函数，它将获取节点的索引和访问过的数组。

1. 保持当前节点标记为已访问，然后打印它。
2. 遍历所有相邻的音符和未标记的音符，并使用相邻节点的索引调用递归函数。

探索我们流行的软件工程课程

特性

数据结构中 DFS 中的时间和空间分析根据其应用领域的不同而有所不同。 理论上，DFS主要用于穿越全图，耗时O(|V|+|E|) 其中|V| 描述顶点数和|E| 描述了边的数量。 该图是线性的。

在这些应用程序中，空间 O(|V|) 也被用作最后的手段，以保留存储在搜索路径上的顶点堆栈和已访问的顶点集。 因此，时间和空间界限的设置类似于广度优先搜索。 在这里，使用的两种算法较少依赖于它们的复杂性，而更多地依赖于两种算法产生的顶点顺序的各种特征。

当涉及到 DFS 在与特定领域相关的数据结构中的应用时，例如在网络爬虫或 AI 中寻找解决方案时，需要遍历的图可能太大而无法全部访问。 在这种情况下，搜索只执行到有限的深度； 由于有限的资源，如磁盘空间或内存。 数据结构通常不用于跟踪之前访问过的所有顶点的集合。 当涉及到扩展边和顶点的单位时，执行到有限深度的搜索仍然使时间线性化。

但是，请记住，此数字与整个图的大小不同，因为某些顶点可能会被搜索多次，而另一些则不会被搜索。

在这种情况下，DFS 还转向启发式方法来选择更有希望的分支。 最后，当无法确定适当的深度限制时，通过一系列增长限制重复应用先验的、迭代的加深 DFS。

从世界顶级大学在线学习软件开发课程。 获得行政 PG 课程、高级证书课程或硕士课程，以加快您的职业生涯。

深度优先搜索算法

标准 DFS 实现中图的每个顶点都分为两类：

1. 未访问
2. 参观过

该算法用于精确定位每个顶点并将它们标记为已访问，同时避免循环。

这是 DFS 算法的工作原理：

1. 将图的任何特定顶点放在堆栈上。
2. 堆栈顶部的项目应添加到访问列表中。
3. 制作该顶点的相邻节点列表，并将那些不在访问列表中的节点添加到堆栈顶部。
4. 继续重复前面的步骤，直到堆栈清空。

DFS 排序

顶点排序：在 DFS 中有四种方法可以对图或树的顶点进行线性排序：

1. DFS 算法首先访问的顶点列表被称为预排序。 这是描述搜索进度的简洁方式。
2. 按算法最后访问的顺序排列的顶点列表称为后排序。
3. 与第一次访问顺序相反的顶点列表是反向预排序。 因此，不应将其误认为是后订购。
4. 与上次访问顺序相反的顶点列表是反向后排序。 不应将其误认为是预购。

此外，二叉树还存在有序和逆序。

图的深度优先搜索或 DFS

图的 DFS 与树的 DFS 几乎相同。 唯一的区别是图可能有循环，不像树。 一个节点可能会被访问​​多次，为了避免处理该节点，使用了一个布尔访问数组。

深度优先搜索的输出

深度优先搜索更容易用搜索中已经到达的顶点的生成树来描述。 基于此生成树，原始图边分为三类：树的节点指向其后代之一的前向边、节点指向其祖先之一的后向边和交叉边，它不执行前面的任何功能。

深度优先遍历 (DFS) 的应用

深度优先搜索在以下算法中用作构建块：

• 搜索已连接的组件。
• 查找 2-（顶点或边）连接的组件。
• 寻找图表的桥梁。
• 查找 3（顶点或边）连接的组件。
• 拓扑排序。
• 查找强连接的组件。
• 找出一个物种是否与系统发育树中的一个或另一个物种相似。
• 平面度测试。
• 产生词来确定任何组的极限集。
• 解决只有一种解决方案的谜题，例如迷宫。
• 迷宫一代。
• 在图中搜索双连通性。

DFS 伪代码和 Python 实现

init() 函数在下面伪代码中的每个节点上运行，以确保访问所有顶点。 这一点尤其重要，因为图表可能有各种不连贯的区域。

这是伪代码：

DFS(G, u)

u.visited = true

对于每个 v ∈ G.Adj[u]

如果 v.visited == false

DFS(G,v)

在里面（） {

对于每个 u ∈ G

u.visited = 假

对于每个 u ∈ G

DFS(G, u)

}

这是 Python 中的 DFS 实现：

图 = {

'5' : ['3','7'],

'2' : ['1', '3'],

'6' : ['7'],

'3' : [],

'4' : ['6'],

“7”：[]

}

访问=设置（）

def dfs（已访问，图形，节点）：

如果节点未访问：

打印（节点）

访问过的.add（节点）

对于图[节点]中的邻居：

dfs（已访问、图表、邻居）

print(“这是 DFS:”)

dfs（已访问，图表，'5'）

输出：

这是 DFS：5

探索我们流行的软件工程课程

深度优先搜索的复杂性

John Reif 探索了深度优先搜索的计算复杂性。 准确地说，在一个图中，给定的事实是 G，让 O 是由重复 DFS 算法确定的标准阶。 G代表图，O代表冗余DFS算法的排序输出。 此输出称为词典 DFS 排序。

结论

DFS 算法的主要目标是访问避免目标图中循环的每个顶点。 如果您希望参与搜索操作或排序操作的高级实现，您绝对应该考虑学习深度优先搜索和数据结构的高级和整体课程。

upGrad有一些顶级的 DFS 课程，如计算机科学硕士和大数据专业。

如果您正在努力迈出下一步并寻求专家建议， upGrad Mentorship旨在为您提供与业内最佳职业顾问和专家的一对一课程。