Python 算法基础篇之图的遍历算法：深度优先搜索和广度优先搜索

Python 算法基础篇之图的遍历算法：深度优先搜索和广度优先搜索

引言

图的遍历是计算机科学中的一项重要任务，用于查找和访问图中的所有节点。深度优先搜索（ DFS ）和广度优先搜索（ BFS ）是两种常用的图遍历算法。本篇博客将重点介绍这两种算法的原理、应用场景以及使用 Python 实现，并通过实例演示每一行代码的运行过程。

😃😄 ❤️ ❤️ ❤️

1. 图的遍历概述

在图中，遍历是指通过一定的方式访问图中的所有节点。图的遍历是一种常见的问题，例如查找图中是否存在某个节点，查找两个节点之间的路径，或者查找图中的连通分量等。

图的遍历算法可以分为深度优先搜索（ DFS ）和广度优先搜索（ BFS ）。这两种算法在不同场景下有不同的优势，深度优先搜索通常用于查找路径和连通分量等问题，广度优先搜索通常用于查找最短路径等问题。

2. 深度优先搜索（ DFS ）

深度优先搜索是一种递归的图遍历算法，其基本思想是从起始节点开始，沿着一条路径访问图中的节点，直到无法继续访问为止，然后回溯到上一个节点，继续访问其他的路径，直到遍历完所有节点。

2.1 DFS 的实现

下面是深度优先搜索算法的 Python 实现：

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)
    return visited

代码解释：上述代码定义了一个深度优先搜索函数 dfs ，该函数接收一个图 graph 、起始节点 node 和一个空的已访问列表 visited 作为参数，并返回遍历后的节点列表。在函数中，我们首先检查当前节点是否已经被访问过，如果没有，则将其添加到已访问列表中，并递归地访问它的所有邻居节点。

2.2 DFS 的应用场景

深度优先搜索在许多场景中都有应用，例如：

• 查找图中两个节点之间是否存在路径；
• 查找图中的连通分量；
• 判断图中是否存在环等。

3. 广度优先搜索（ BFS ）

广度优先搜索是一种非递归的图遍历算法，其基本思想是从起始节点开始，依次访问其所有邻居节点，然后再访问邻居节点的邻居节点，直到遍历完所有节点为止。

3.1 BFS 的实现

下面是广度优先搜索算法的 Python 实现：

from collections import deque

def bfs(graph, start):
    visited = []
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.append(node)
            queue.extend(graph[node])
    return visited

代码解释：上述代码定义了一个广度优先搜索函数 bfs ，该函数接收一个图 graph 和起始节点 start 作为参数，并返回遍历后的节点列表。在函数中，我们使用一个队列 queue 来保存待访问的节点，从起始节点开始，依次将其邻居节点加入队列中，并继续访问邻居节点的邻居节点，直到队列为空。

3.2 BFS 的应用场景

广度优先搜索在许多场景中都有应用，例如：

• 查找图中两个节点之间的最短路径；
• 查找图中的连通分量；
• 拓扑排序等。

4. 示例与实例

现在我们创建一个示例图，并使用深度优先搜索和广度优先搜索进行遍历。

# 创建一个示例图
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D', 'E'],
    'D': ['B', 'C', 'E', 'F'],
    'E': ['C', 'D'],
    'F': ['D']
}

# 使用DFS遍历图
print("深度优先搜索结果：", dfs(graph, 'A', []))

# 使用BFS遍历图
print("广度优先搜索结果：", bfs(graph, 'A'))

运行上述代码，输出结果如下：

深度优先搜索结果： ['A', 'B', 'C', 'D', 'E', 'F']
广度优先搜索结果： ['A', 'B', 'C', 'D', 'E', 'F']

总结

本篇博客重点介绍了图的遍历算法：深度优先搜索和广度优先搜索。深度优先搜索通过递归的方式遍历图中的节点，广度优先搜索通过队列的方式遍历图中的节点。每一种算法都有其特定的应用场景，可以根据具体问题选择合适的算法。

图的遍历是计算机科学中的基础算法，它在图的应用中起到了至关重要的作用，例如社交网络中的好友关系分析、路网中的最短路径规划等。