深度寻路算法-DFS
【摘要】 深度寻路算法(Depth-First Search,DFS)是一种用于遍历或搜索图或树的算法。它从一个起始节点开始,沿着一条路径尽可能深地访问节点,直到到达一个无法访问的节点,然后回溯到最近的一个还未访问完的节点,继续进行深度优先搜索。深度寻路算法可以用递归和非递归两种方式实现。递归实现递归实现深度寻路算法比较简单,代码如下:def dfs_recursive(graph, start, v...
深度寻路算法(Depth-First Search,DFS)是一种用于遍历或搜索图或树的算法。它从一个起始节点开始,沿着一条路径尽可能深地访问节点,直到到达一个无法访问的节点,然后回溯到最近的一个还未访问完的节点,继续进行深度优先搜索。深度寻路算法可以用递归和非递归两种方式实现。
- 递归实现
递归实现深度寻路算法比较简单,代码如下:
def dfs_recursive(graph, start, visited):
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
其中,graph
是一个字典,表示图的邻接表;start
是起始节点;visited
是一个集合,表示已经访问过的节点。
- 非递归实现
非递归实现深度寻路算法需要使用栈来保存节点,代码如下:
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
print(vertex, end=' ')
stack.extend(reversed(graph[vertex]))
其中,graph
是一个字典,表示图的邻接表;start
是起始节点。
- 生成器实现
生成器实现深度寻路算法可以更加简洁地表示算法的本质,代码如下:
def dfs_generator(graph, start, visited=set()):
visited.add(start)
yield start
for neighbor in graph[start] - visited:
yield from dfs_generator(graph, neighbor, visited)
其中,graph
是一个字典,表示图的邻接表;start
是起始节点;visited
是一个集合,表示已经访问过的节点。
以上三种实现方式都是正确的深度寻路算法,具体选择哪种方式取决于具体场景和个人偏好。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)