Python 编程的进阶之路上，掌握图的深度优先遍历（Depth-First Search，简称 DFS）和广度优先遍历（Breadth-First Search，简称 BFS）是至关重要的一步。这两种遍历算法不仅在理论上具有重要意义，在实际应用中也能解决许多复杂的问题。接下来，让我们一起深入学习这两种算法。
首先，我们来了解一下图的基本概念。图由顶点（Vertex）和边（Edge）组成，可以分为有向图和无向图。为了在 Python 中表示图，我们可以使用邻接表或者邻接矩阵的方式。
下面是使用邻接表表示无向图的 Python 代码示例：
class Graph:
def __init__(self):
self.graph = {
}
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
if v in self.graph:
self.graph[v].append(u)
else:
self.graph[v] = [u]
AI 代码解读
有了图的表示，接下来实现 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)
AI 代码解读
为了更好地理解 DFS，假设我们有一个简单的图，顶点为 1 到 5，边为 (1, 2), (1, 3), (2, 4), (2, 5) 。
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 4)
g.add_edge(2, 5)
print("DFS 遍历:")
dfs(g.graph, 1)
AI 代码解读
接下来是 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)
AI 代码解读
同样对于上述的图，进行 BFS 遍历：
print("BFS 遍历:")
bfs(g.graph, 1)
AI 代码解读
在实际应用中，DFS 常用于查找路径、判断图是否连通等问题。而 BFS 则常用于求最短路径、层次遍历等情况。
通过以上的详细讲解和示例代码，相信您对图的 DFS 和 BFS 遍历有了更深入的理解。不断地练习和应用这些知识，您将在 Python 编程的道路上更上一层楼，逐渐成为 Python 大神！
