通过深度优先遍历的方式进行实现
- 时间复杂度:O (n)
空间复杂度:O (n)
function cloneGraph(node) {
if (!node) return;
const visited = new Map();
const dfs = (n) => {
const newNode = new Node(n.val);
visited.set(n, newNode);
(n.neighbors || []).forEach((next) => {
if (!visited.has(next)) {
dfs(next);
}
newNode.neighbors.push(visited.get(next));
});
};
dfs(node);
return visited.get(node);
}
代码中主要访问了图的所有节点,所以时间复杂度是O (n) n 代表节点数,空间复杂度是O (n) ,因为我们定义了 Map 数据结构,里面用来存放所有节点。
这里可能会有同学问,递归的空间复杂度不是递归的深度吗?不是也要算进去吗?因为递归的深度很大可能性是小于 Map 的长度的,所以我们以空间复杂度最大值为准。
通过广度优先遍历的方式进行实现
- 时间复杂度:O (n)
空间复杂度:O (n)
function cloneGraph(node) {
if (!node) return;
const visited = new Map();
visited.set(node, new Node(node.val));
const q = [node];
while (q.length) {
const n = q.shift();
(n.neighbors || []).forEach((next) => {
if (!visited.has(next)) {
q.push(next);
visited.set(next, new Node(next.val));
}
visited.get(n).neighbors.push(visited.get(next));
});
}
return visited.get(node);
}
首先时间复杂度依然是 O (n) ,n 代表所有节点数,因为广度优先遍历会访问图的所有节点。空间复杂度为 O (n) 因为我们使用了队列,队列的长度最坏情况下可能是所有的节点数。