python深度优先搜索算法怎么实现

117次阅读

共计 898 个字符，预计需要花费 3 分钟才能阅读完成。

深度优先搜索（Depth First Search，DFS）是一种常用的图遍历算法，可以使用递归或者栈来实现。
递归实现深度优先搜索算法可以按照以下步骤进行：

定义一个 DFS 函数，参数为当前节点和访问状态的集合，初始状态为未访问。
将当前节点标记为已访问。
遍历当前节点的邻接节点，如果邻接节点未访问，则递归调用 DFS 函数。
递归调用 DFS 函数后，回溯到上一个节点，继续遍历下一个未访问的邻接节点。

以下是一个使用递归实现深度优先搜索的例子：

def dfs(node, visited):
visited.add(node)  # 标记当前节点为已访问
# 遍历当前节点的邻接节点
for neighbor in node.neighbors:
if neighbor not in visited:  # 如果邻接节点未访问，则递归调用 DFS 函数
dfs(neighbor, visited)
# 使用示例
visited = set()  # 记录访问状态的集合
dfs(start_node, visited)

如果不使用递归，可以使用栈来实现深度优先搜索算法。栈的原理是先进后出，可以用来保存待访问的节点。具体步骤如下：

创建一个栈，并将起始节点入栈。
创建一个集合来记录节点的访问状态。
进入循环，直到栈为空：

弹出栈顶节点，并将其标记为已访问。
遍历当前节点的邻接节点，如果邻接节点未访问，则将其入栈。

以下是一个使用栈实现深度优先搜索的例子：

def dfs(start_node):
stack = [start_node]  # 创建一个栈，并将起始节点入栈
visited = set()  # 记录访问状态的集合
while stack:
node = stack.pop()  # 弹出栈顶节点
visited.add(node)  # 标记当前节点为已访问
# 遍历当前节点的邻接节点
for neighbor in node.neighbors:
if neighbor not in visited:  # 如果邻接节点未访问，则将其入栈
stack.append(neighbor)
# 使用示例
dfs(start_node)

以上是两种常见的深度优先搜索算法的实现方式，可以根据具体的需求选择适合的方法来实现。

丸趣 TV 网 – 提供最优质的资源集合！

正文完