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

图遍历算法 DFS/BFS 实战3种邻接表实现与LeetCode 133题解邻接表作为图的经典存储结构在算法面试和实际工程中都有广泛应用。本文将手把手带你实现邻接表的三种遍历方式并通过LeetCode 133题克隆图的实战掌握DFS和BFS的核心思想与代码技巧。1. 邻接表基础与实现邻接表使用数组链表的形式存储图结构适合表示稀疏图。我们首先定义图的节点结构class Node { public int val; public ListNode neighbors; public Node(int _val) { val _val; neighbors new ArrayListNode(); } }邻接表相比邻接矩阵的优势在于空间效率仅存储实际存在的边空间复杂度O(VE)遍历效率直接获取某节点的所有邻接点无需遍历整个矩阵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(VE)空间复杂度O(V)2.2 栈实现DFS非递归递归可能引发栈溢出工业级代码常使用显式栈void dfsWithStack(Node start) { SetInteger visited new HashSet(); DequeNode 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 MapNode, 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对比特性DFSBFS数据结构栈队列空间复杂度O(V)O(V)适用场景拓扑排序、连通性问题最短路径、层级遍历内存访问局部性好可能引发更多缺页中断5.2 性能优化技巧剪枝优化在遍历过程中提前终止不必要的分支双向BFS当目标节点已知时从起点和终点同时搜索迭代加深结合DFS的空间效率和BFS的完备性// 双向BFS示例 public Node bidirectionalBFSClone(Node node) { if (node null) return null; MapNode, Node forwardVisited new HashMap(); MapNode, Node backwardVisited new HashMap(); DequeNode forwardQueue new ArrayDeque(); DequeNode 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题目巩固所学课程表拓扑排序岛屿数量连通分量单词接龙最短路径