亲爱的读者，在本文中，我将向您介绍深度优先搜索（DFS）的概念。这是一个图形概念，是许多竞争性编码考试中的常见问题。那么，让我们看看如何使用 Python 创建 DFS 遍历。
什么是深度优先搜索？
深度优先搜索是一种利用Stack数据结构来遍历图和树的算法。深度优先搜索的概念来源于“深度”一词。树遍历直到分支的深度，然后返回遍历到其余节点。
考虑一个空的“堆栈”，其中包含每次迭代访问的节点。我们在这里的任务如下：
- 从根节点开始并将其压入堆栈。
- 检查树的任何相邻节点并选择一个节点。
- 遍历选中节点的整个分支，将所有节点压入栈中。
- 当到达分支末端时（不再有相邻节点），即第 n 个叶节点，向后移动一步并查找第 n-1 个节点的相邻节点。
- 如果第n-1个节点有相邻节点，则遍历这些分支并将节点压入堆栈。
深度优先搜索的概念图示
让我们看看下面的示例图：
A是根节点。因此，由于 A 被访问，我们将其压入堆栈。
Stack : A |
我们去AB分行吧。B 未被访问，因此我们转到 B 并将 B 压入堆栈。
Stack : A B |
现在，我们已经到达 AB 分支的末尾，我们移动到第 n-1 个节点，即 A。我们现在将查看 A 的相邻节点，即 S。访问 S 并将其压入堆栈。现在你必须遍历 SCD 分支，直到深度，即直到 D 并将 S、C、D 标记为已访问。
Stack: A B S C D |
由于D没有其他相邻节点，所以回到C并遍历其相邻分支EHG到深度并将它们压入堆栈。
Stack : A B S C D E H G |
到达 D 时，只有一个相邻节点（即 F）未被访问。将 F 也压入堆栈。
Stack : A B S C D E H G F |
这个栈本身就是DFS的遍历。
用 Python 编写深度优先搜索算法
您必须知道，有多种表示图的方法，即邻接表和邻接矩阵。
因此，在下面的示例中，我为图中的每个节点定义了一个邻接列表。
graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G']} |
注意：该邻接列表可以由用户输入，不需要硬编码。
现在，我们将定义 DFS 函数，该函数接受 3 个参数作为输入：图（邻接表）、节点和已访问节点列表。
如果当前节点未被访问，即不存在于访问列表中，则将其标记为已访问并将其追加到访问列表中。
移动到下一个节点，然后递归地将这个节点传递给 DFS 函数。这样每个节点都会移动到深度并将其打印为 DFS 输出。
def dfs(graph, node, visited): if node not in visited: visited.append(node) for k in graph[node]: dfs(graph,k, visited) return visitedvisited = dfs(graph1,'A', [])print(visited) |
完整的代码和输出
graph1 = { 'A' : ['B','S'], 'B' : ['A'], 'C' : ['D','E','F','S'], 'D' : ['C'], 'E' : ['C','H'], 'F' : ['C','G'], 'G' : ['F','S'], 'H' : ['E','G'], 'S' : ['A','C','G']}def dfs(graph, node, visited): if node not in visited: visited.append(node) for k in graph[node]: dfs(graph,k, visited) return visitedvisited = dfs(graph1,'A', [])print(visited) |
上述代码的输出如下：
['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F'] |
结论
我希望您已经阅读了有关 DFS 算法的教程，并且也能够理解代码和示例。请在身边使用笔和纸尝试一下，以便更好地理解遍历过程。