4.0 KiB

Raw Permalink Blame History

使用 Python 的深度优先搜索算法

原文：https://www.askpython.com/python/examples/depth-first-search-algorithm

亲爱的读者，在本文中，我将带你了解深度优先搜索(DFS)的概念。这是一个图的概念，是很多竞争性编码考试中常见的问题。因此，让我们看看如何使用 Python 创建一个 DFS 遍历。

什么是深度优先搜索？

深度优先搜索是一种利用堆栈数据结构遍历图形和树的算法。深度优先搜索的概念来源于“深度”这个词。该树遍历到一个分支的深度，然后返回到其余的节点。

考虑一个空的“堆栈”,它包含每次迭代访问的节点。我们在这里的任务如下:

从根节点开始，将其推送到堆栈上。
检查树的任何相邻节点，并选择一个节点。
遍历所选节点的整个分支，并将所有节点推入堆栈。
在到达分支的末端(没有更多相邻节点)即第 n 个叶节点时，向后移动一步并寻找第 n-1 个节点的相邻节点。
如果第 n-1 个节点有相邻的节点，则遍历这些分支并将节点推送到堆栈上。

深度优先搜索的概念说明

让我们看看下面的示例图:

Example Graph

是根节点。既然 A 被访问了，我们就把它推到堆栈上。

Stack : A

我们转到分支 A-B，B 没有被访问，所以我们转到 B，把 B 推送到栈上。

Stack : A B

现在，我们已经到达 A-B 分支的末尾，我们移动到第 n-1 个节点 A。我们现在将查看 A 的相邻节点 S。访问 S 并将其推送到堆栈上。现在，您必须遍历 S-C-D 分支，直到深度即到达 D，并将 S、C、D 标记为已访问。

Stack: A B S C D

因为 D 没有其他相邻节点，所以移回 C，遍历其相邻分支 E-H-G 到深度，并将它们推送到堆栈上。

Stack : A B S C D E H G

到达 D 时，只有一个相邻节点 ie 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 visited

visited = 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 visited

visited = dfs(graph1,'A', [])
print(visited)

上述代码的输出如下:

['A', 'B', 'S', 'C', 'D', 'E', 'H', 'G', 'F']

结论

我希望你已经学习了这篇关于 DFS 算法的教程，并且能够理解代码和例子。一定要用你身边的纸和笔来尝试，以便更好地理解这些遍历。

4.0 KiB Raw Permalink Blame History Unescape Escape