Python 中的 DFS (深度优先搜索)

在本教程中，我们将学习深度优先搜索算法，并用 Python 编程语言实现它。我们将讨论它的基础和简单性。该算法用于解决图相关问题，这对于许多竞争性考试都很有帮助。DFS 是一种遍历算法，用于遍历图或树中的所有元素或搜索元素。让我们对 DFS 进行基本介绍。

深度优先搜索简介

DFS 是一种用于遍历图或树数据结构中目标节点的算法。深度优先搜索源自“深度”一词。它优先考虑深度，沿着一条分支进行搜索，直到分支的末端。在 Python 中，我们可以轻松地使用递归和其他数据结构（如字典和集合）来实现它。

图的表示

在实现 DFS 算法之前，我们将尝试理解如何在 Python 中表示图。

图有几种版本。图可能在两个节点之间具有有向边（定义源和目标），或者具有无向边。有向图可以带有权重。它完全取决于应用程序来使用其中任何一个图的版本。

为了实现 DFS，我们将使用带有有向边的图，以便遍历整个图。

Python 提供了多种方法来在 Python 中表示图；以下是最常见的方法。

• 邻接矩阵
• 邻接表

邻接矩阵

邻接矩阵是一个 N x N 的方阵（其中 N 是图中节点的数量）。

每一行代表一个节点；每一列代表该节点的潜在子节点。每一对 (行, 列) 代表一个潜在的边。位置 (i, j) 处的非零值表示 i 和 j 之间存在一条边。如果值为零，则表示 i 和 j 之间没有边。

在非加权图中可以使用二元数字（1 表示边存在，0 表示不存在）。

例如，位置 (2, 3) 之间的值 15 表示节点 2 和 3 之间存在一条权重为 15 的边。

我们可以使用二维 Numpy 数组来表示邻接矩阵。

邻接表

它是一个由多个列表组成的集合。每个列表代表图中的一个节点，并存储该节点的所有邻居/子节点。

我们可以使用字典来表示邻接列表，其中键是图的节点，值是一个列表，包含这些节点的邻居。

让我们以一个简单的图为例，并用字典表示它。

上面的图有四条边。

A -> B

A -> C

B -> C

C -> D

让我们创建一个 Python 字典来表示这个图。

现在我们对如何在 Python 中表示图有了一个想法。让我们实现 DFS 算法。

实现深度优先搜索（非递归方法）

让我们考虑以下图用于 DFS 实现。

让我们使用 Python 字典将图定义为邻接列表。

我们可以使用递归技术和非递归技术（迭代方法）来实现 DFS。

在本节中，我们将了解迭代方法。

我们将使用栈和列表来跟踪已访问的节点。

• 首先，我们将访问根节点并将其标记为已访问。然后，我们将将其所有邻居推送到栈中。
• 在每一步，我们将从栈中弹出一个元素，并检查它是否已被访问。
• 如果节点未被访问，它将被添加到路径中，并且其所有邻居将被添加到栈中。

DFS 伪代码

以下是 DFS 的伪代码。在 init() 函数中，我们对每个节点运行 DFS 函数，因为在大多数情况下，图可能包含两个不同的不连通部分。因此，它确保我们覆盖每个顶点，也可以对每个节点运行 DFS 算法。

注意 - 上面的伪代码是用于递归方法的。

让我们使用 Python 代码实现 DFS。

示例 -

输出

A D H C F J G K B E I

图的遍历顺序是“深度优先”的方式。

使用递归方法的 DFS

递归是一种流行的解决问题的方法，其中相同的问题被分解为更小的实例。我们将在程序中定义基本情况。让我们理解下面的例子。

示例 -

输出

['A', 'B', 'E', 'I', 'C', 'G', 'K', 'F', 'J', 'D', 'H']

遍历顺序再次是深度优先的方式。

复杂度

DFS 的时间复杂度表示为 O(V+E)，其中 V 表示节点数，E 表示边数。空间复杂度为 0(V)。

算法的应用

以下是 DFS 的实际应用。

• 它用于查找路径。
• 它用于测试图是否为二分图。
• 它用于查找图的强连通分量。
• 它用于检测图中的环。
• 它用于调度问题。
• 它用于拓扑排序。

结论

本教程包括 Python 中深度优先搜索的概念，该概念用于遍历图或树。我们讨论了在 Python 中实现 DFS 的递归和非递归方法。我们还定义了如何在 Python 中表示图。