图遍历算法 DFS/BFS 实战：3种邻接表实现与LeetCode 133题解-平芜编程栈

图遍历算法 DFS/BFS 实战：3种邻接表实现与LeetCode 133题解

邻接表作为图的经典存储结构，在算法面试和实际工程中都有广泛应用。本文将手把手带你实现邻接表的三种遍历方式，并通过LeetCode 133题"克隆图"的实战，掌握DFS和BFS的核心思想与代码技巧。

1. 邻接表基础与实现

邻接表使用数组+链表的形式存储图结构，适合表示稀疏图。我们首先定义图的节点结构：

class Node { public int val; public List<Node> neighbors; public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } }

邻接表相比邻接矩阵的优势在于：

空间效率：仅存储实际存在的边，空间复杂度O(V+E)
遍历效率：直接获取某节点的所有邻接点，无需遍历整个矩阵

2. 深度优先遍历(DFS)的两种实现

2.1 递归实现DFS

递归是最直观的DFS实现方式，利用系统调用栈自动保存状态：

def dfs_recursive(node, visited): if not node: return visited.add(node.val) print(node.val) # 处理当前节点 for neighbor in node.neighbors: if neighbor.val not in visited: dfs_recursive(neighbor, visited)

关键点：

使用visited集合避免重复访问
前序处理（先访问父节点再访问子节点）
时间复杂度O(V+E)，空间复杂度O(V)

2.2 栈实现DFS（非递归）

递归可能引发栈溢出，工业级代码常使用显式栈：

void dfsWithStack(Node start) { Set<Integer> visited = new HashSet<>(); Deque<Node> stack = new ArrayDeque<>(); stack.push(start); while (!stack.isEmpty()) { Node current = stack.pop(); if (visited.contains(current.val)) continue; visited.add(current.val); System.out.println(current.val); // 处理节点 // 逆序压栈保证遍历顺序 for (int i = current.neighbors.size()-1; i >=0; i--) { Node neighbor = current.neighbors.get(i); if (!visited.contains(neighbor.val)) { stack.push(neighbor); } } } }

性能对比：

实现方式	空间复杂度	适用场景
递归	O(V)	树深度可控时代码简洁
栈	O(V)	避免栈溢出风险

3. 广度优先遍历(BFS)实现

BFS使用队列实现层级遍历，适合最短路径类问题：

from collections import deque def bfs(start): visited = set() queue = deque([start]) visited.add(start.val) while queue: node = queue.popleft() print(node.val) # 处理当前节点 for neighbor in node.neighbors: if neighbor.val not in visited: visited.add(neighbor.val) queue.append(neighbor)

BFS核心特性：

队列保证先进先出的访问顺序
天然解决无权图的最短路径问题
需要额外空间存储队列，空间复杂度O(V)

4. LeetCode 133克隆图实战

4.1 问题分析

题目要求深拷贝一个无向连通图，难点在于：

避免重复创建相同节点
正确处理邻居关系的复制

4.2 DFS解法

class Solution { private Map<Node, Node> visited = new HashMap<>(); public Node cloneGraph(Node node) { if (node == null) return null; if (visited.containsKey(node)) { return visited.get(node); } Node clone = new Node(node.val); visited.put(node, clone); for (Node neighbor : node.neighbors) { clone.neighbors.add(cloneGraph(neighbor)); } return clone; } }

解决思路：

使用HashMap记录原节点与克隆节点的映射
递归处理每个节点的邻居
遇到已访问节点直接返回克隆节点

4.3 BFS解法

from collections import deque class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None visited = {} queue = deque([node]) visited[node] = Node(node.val) while queue: current = queue.popleft() for neighbor in current.neighbors: if neighbor not in visited: visited[neighbor] = Node(neighbor.val) queue.append(neighbor) visited[current].neighbors.append(visited[neighbor]) return visited[node]

BFS优势：

非递归实现避免栈溢出
层级遍历保证克隆顺序
适合大规模图的克隆

5. 算法选择与性能优化

5.1 DFS vs BFS对比

特性	DFS	BFS
数据结构	栈	队列
空间复杂度	O(V)	O(V)
适用场景	拓扑排序、连通性问题	最短路径、层级遍历
内存访问	局部性好	可能引发更多缺页中断

5.2 性能优化技巧

剪枝优化：在遍历过程中提前终止不必要的分支
双向BFS：当目标节点已知时，从起点和终点同时搜索
迭代加深：结合DFS的空间效率和BFS的完备性

// 双向BFS示例 public Node bidirectionalBFSClone(Node node) { if (node == null) return null; Map<Node, Node> forwardVisited = new HashMap<>(); Map<Node, Node> backwardVisited = new HashMap<>(); Deque<Node> forwardQueue = new ArrayDeque<>(); Deque<Node> backwardQueue = new ArrayDeque<>(); forwardQueue.offer(node); forwardVisited.put(node, new Node(node.val)); while (!forwardQueue.isEmpty() || !backwardQueue.isEmpty()) { if (!forwardQueue.isEmpty()) { Node current = forwardQueue.poll(); // 处理正向遍历... } if (!backwardQueue.isEmpty()) { Node current = backwardQueue.poll(); // 处理反向遍历... } } return forwardVisited.get(node); }

6. 工程实践中的注意事项

循环引用处理：图中可能存在环，必须记录已访问节点
大规模图优化：
- 使用位图代替哈希表减少内存占用
- 考虑分块处理超大规模图
并行化可能：BFS的层级特性使其更适合并行化处理

# 并行BFS示例（伪代码） def parallel_bfs(start): visited = ConcurrentHashSet() current_level = [start] while current_level: next_level = [] with ThreadPoolExecutor() as executor: for node in current_level: if node not in visited: visited.add(node) # 处理节点... neighbors = get_unvisited_neighbors(node) next_level.extend(neighbors) current_level = next_level

掌握图的遍历算法不仅是面试必备技能，更是解决实际工程问题的基础工具。建议读者在理解本文代码后，继续挑战以下LeetCode题目巩固所学：