AlgoViz Lab交互式算法学习Algorithms first
克隆图 · 交互式算法学习
深拷贝一个无向连通图。
#133 · 图
克隆图
Clone Graph
adjList = [[2,4],[1,3],[2,4],[1,3]]树 / 图3 个关键状态
步骤 1节点 1 入队并创建副本。
queue=[1]推荐
BFS + 节点映射
时间
O(V+E)空间 O(V)队列逐节点创建尚未克隆的邻居并连接。
1function cloneGraph(node) {2 if (!node) return null;3 const map = new Map([4 [node, {5 val: node.val,6 neighbors: []7 }]8 ]),9 q = [node];10 while (q.length) {11 const cur = q.shift();12 for (const n of cur.neighbors) {13 if (!map.has(n)) {14 map.set(n, {15 val: n.val,16 neighbors: []17 });18 q.push(n)19 }20 map.get(cur).neighbors.push(map.get(n));21 }22 }23 return map.get(node);24}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/*2// Definition for a Node.3class Node {4 public int val;5 public List<Node> neighbors;6 public Node() {7 val = 0;8 neighbors = new ArrayList<Node>();9 }10 public Node(int _val) {11 val = _val;12 neighbors = new ArrayList<Node>();13 }14 public Node(int _val, ArrayList<Node> _neighbors) {15 val = _val;16 neighbors = _neighbors;17 }18}19*/20 21class Solution {22 private Map<Node, Node> g = new HashMap<>();23 24 public Node cloneGraph(Node node) {25 return dfs(node);26 }27 28 private Node dfs(Node node) {29 if (node == null) {30 return null;31 }32 Node cloned = g.get(node);33 if (cloned == null) {34 cloned = new Node(node.val);35 g.put(node, cloned);36 for (Node nxt : node.neighbors) {37 cloned.neighbors.add(dfs(nxt));38 }39 }40 return cloned;41 }42}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
克隆图 · 解法对比
深拷贝一个无向连通图。
- 测试用例
adjList = [[2,4],[1,3],[2,4],[1,3]]- 题目分类
- 图
- 解法对比
- 2
DFS + 节点映射
首次访问节点时创建副本，再递归克隆邻居。
- 时间
O(V+E)- 空间
O(V)
BFS + 节点映射
队列逐节点创建尚未克隆的邻居并连接。
- 时间
O(V+E)- 空间
O(V)