前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >深度寻路算法-DFS

深度寻路算法-DFS

原创
作者头像
疯狂的KK
发布2023-03-26 12:14:33
66200
代码可运行
发布2023-03-26 12:14:33
举报
文章被收录于专栏:Java项目实战Java项目实战
运行总次数:0
代码可运行

深度寻路算法(Depth-First Search,DFS)是一种用于遍历或搜索图或树的算法。它从一个起始节点开始,沿着一条路径尽可能深地访问节点,直到到达一个无法访问的节点,然后回溯到最近的一个还未访问完的节点,继续进行深度优先搜索。深度寻路算法可以用递归和非递归两种方式实现。

  1. 递归实现

递归实现深度寻路算法比较简单,代码如下:

代码语言:python
代码运行次数:0
复制
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 是一个集合,表示已经访问过的节点。

  1. 非递归实现

非递归实现深度寻路算法需要使用栈来保存节点,代码如下:

代码语言:python
代码运行次数:0
复制
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 是起始节点。

  1. 生成器实现

生成器实现深度寻路算法可以更加简洁地表示算法的本质,代码如下:

代码语言:python
代码运行次数:0
复制
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 是一个集合,表示已经访问过的节点。

以上三种实现方式都是正确的深度寻路算法,具体选择哪种方式取决于具体场景和个人偏好。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档