逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形

在数据结构的广袤领域中，图是一种强大而复杂的结构，而深度优先搜索（DFS）和广度优先搜索（BFS）则是遍历图的两把利剑。Python 以其简洁和强大的特性，为我们提供了实现和运用这两种算法的便捷途径。

首先，让我们来理解一下图的基本概念。图由顶点（vertex）和边（edge）组成，可以分为有向图和无向图。在 Python 中，我们可以使用多种方式来表示图，如邻接表、邻接矩阵等。

接下来，深入探讨 DFS 算法。DFS 是一种沿着图的深度进行遍历的算法，它优先访问一条路径上的顶点，直到无法继续，然后回溯。

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

下面通过一个示例来展示 DFS 的应用。假设我们有一个无向图，顶点为 1 到 5，边为 (1, 2), (1, 3), (2, 4), (2, 5) 。

graph = {
   
    1: [2, 3],
    2: [1, 4, 5],
    3: [1],
    4: [2],
    5: [2]
}

print("DFS 遍历:")
dfs(graph, 1)

再看 BFS 算法，它是逐层遍历图的算法，先访问距离起始顶点最近的一层顶点，然后再依次访问更远的层。

from collections import deque

def bfs(graph, start):
    visited = {
   start}
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        print(vertex)

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

同样，对于上述的图，进行 BFS 遍历：

print("BFS 遍历:")
bfs(graph, 1)

DFS 和 BFS 在实际应用中各有其优势。DFS 常用于探索路径、检测环路等问题。例如，在迷宫求解中，DFS 可以帮助我们找到一条可能的出路。

BFS 则适用于寻找最短路径问题，比如在网络路由中确定两个节点之间的最短跳数。

无论是处理复杂的网络结构，还是解决实际问题中的路径规划，掌握 Python 中的 DFS 和 BFS 算法，都能让我们在数据结构的世界中披荆斩棘，轻松应对各种难题。

不断练习和应用这些算法，您将在编程的道路上实现逆袭，让图的处理不再是难题，而是展现您技术实力的舞台。