Python递归实现图的深度优先搜索算法

2023-04-15 00:00:00 算法 递归 深度

实现思路：

  1. 定义一个 dfs 函数，接收三个参数：graph（图）、visited（已访问的节点列表）、node（当前节点）。

  2. 首先将当前节点标记为已访问，然后打印该节点。

  3. 遍历当前节点的所有邻居节点，如果邻居节点没有被访问过，则递归调用 dfs 函数，访问该邻居节点。

  4. 代码中使用了一个字典来表示图，其中字典的 key 是节点，value 是该节点的所有邻居节点构成的列表。

代码演示：

graph = {'pidancode.com': ['python', 'java', 'c++', 'javascript'],
         'python': ['numpy', 'pandas', 'matplotlib'],
         'java': ['spring', 'mybatis', 'hibernate'],
         'c++': ['boost', 'linux', 'qt'],
         'javascript': ['vue', 'react'],
         'numpy': [],
         'pandas': [],
         'matplotlib': [],
         'spring': [],
         'mybatis': [],
         'hibernate': [],
         'boost': [],
         'linux': [],
         'qt': [],
         'vue': [],
         'react': []}

visited = set()  # 初始化已访问的节点列表

def dfs(graph, visited, node):
    if node not in visited:
        visited.add(node)  # 标记当前节点为已访问
        print(node)
        for neighbor in graph[node]:  # 遍历邻居节点
            dfs(graph, visited, neighbor)  # 递归调用dfs函数

dfs(graph, visited, 'pidancode.com')  # 从pidancode.com节点开始遍历

输出结果：

pidancode.com
python
numpy
pandas
matplotlib
java
spring
mybatis
hibernate
c++
boost
linux
qt
javascript
vue
react

相关文章