如何用Python编写深度优先搜索算法？
深度优先搜索（Depth-First Search，简称DFS）是一种常用的图遍历算法。在深度优先搜索中，从起始节点开始，不断探索邻接节点，直至无法继续探索，然后回退到上一节点，继续遍历还未探索的邻接节点，直至所有节点都被访问。
下面是一个用Python编写的深度优先搜索算法示例：
# 定义图的类class Graph: def __init__(self, vertices): self.V = vertices # 节点数量 self.adj = [[] for _ in range(self.V)] # 存储节点的邻接节点 # 添加边 def add_edge(self, u, v): self.adj[u].append(v) # DFS递归函数 def dfs_util(self, u, visited): visited[u] = True # 标记当前节点为已访问 print(u, end=' ') # 输出当前节点 # 遍历当前节点的所有邻接节点 for i in self.adj[u]: if not visited[i]: self.dfs_util(i, visited) # 对外接口，执行DFS def dfs(self, u): visited = [False] * self.V # 标记所有节点均未访问 self.dfs_util(u, visited) # 测试代码if __name__ == '__main__': # 创建一个具有4个节点的图 g = Graph(4) # 添加图的边 g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 0) g.add_edge(2, 3) g.add_edge(3, 3) print("深度优先遍历结果：") g.dfs(2)
以上代码实现了一个Graph类来表示图的结构，其中包含了初始化节点数量和邻接节点的定义。接着定义了添加边的函数add_edge。
立即学习“Python免费学习笔记（深入）”；
DFS算法在dfs_util递归函数的辅助下进行，函数接受两个参数：当前节点u和一个数组visited，用于标记节点是否已经访问。算法首先将当前节点标记为已访问，并输出该节点的值。然后遍历当前节点的所有邻接节点，如果邻接节点尚未被访问，则递归调用dfs_util函数。
最后，dfs函数作为对外接口，接受起始节点作为参数，并创建一个visited数组初始化为False。调用dfs_util函数开始DFS遍历。
在测试代码中，我们创建了一个具有4个节点的图，并添加了一些边。然后使用起始节点2进行DFS遍历，并输出结果。
希望这个代码示例能够帮助你理解如何用Python编写深度优先搜索算法。你也可以根据自己的需求对代码进行修改和优化。
以上就是如何用Python编写深度优先搜索算法？的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1342970.html
微信扫一扫 
支付宝扫一扫 
