### Python 实现图的深度优先遍历（DFS）和广度优先遍历（BFS） 以下是基于邻接表实现的 `Graph` 类，支持深度优先搜索 (DFS) 和广度优先搜索 (BFS) 的具体代码： #### 图的定义与初始化 通过创建一个类来表示图，并使用字典作为数据结构存储节点及其相邻节点。 ```python class Graph: def __init__(self): self.graph = {} def add_edge(self, u, v): if u not in self.graph: self.graph[u] = [] if v not in self.graph: self.graph[v] = [] self.graph[u].append(v) def dfs_util(self, node, visited): visited.add(node) print(node, end=" ") for neighbor in self.graph.get(node, []): if neighbor not in visited: self.dfs_util(neighbor, visited) def dfs(self, start_node): visited = set() print("Depth First Traversal:") self.dfs_util(start_node, visited) print() def bfs(self, start_node): visited = set() queue = [] visited.add(start_node) queue.append(start_node) print("Breadth First Traversal:") while queue: current_node = queue.pop(0) print(current_node, end=" ") for neighbor in self.graph.get(current_node, []): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) print() ``` #### 使用示例 以下是一个简单的例子，展示如何构建图并执行 DFS 和 BFS 遍历。 ```python if __name__ == "__main__": g = Graph() g.add_edge('A', 'B') g.add_edge('A', 'C') g.add_edge('B', 'D') g.add_edge('B', 'E') g.add_edge('C', 'F') g.dfs('A') # 输出 Depth First Traversal 结果 g.bfs('A') # 输出 Breadth First Traversal 结果 ``` 运行上述代码会得到如下输出： ``` Depth First Traversal: A B D E C F Breadth First Traversal: A B C D E F ``` --- ### 关键概念解释 - **深度优先遍历 (DFS)** 是一种递归方法，在访问某个顶点后继续沿着其未被访问过的邻居深入探索，直到无法再前进为止。之后回溯至上一层次寻找其他可能路径[^2]。 - **广度优先遍历 (BFS)** 则采用队列机制逐层扩展当前已知的所有可达节点，确保同一层级内的所有节点均先于更深层次级中的任何节点被处理完毕[^3]。 ---