克隆图
# 📃 题目描述
题目链接:133. 克隆图 (opens new window)
# 🔔 解题思路
# DFS
对于本题而言,我们需要明确图的深拷贝是在做什么,对于一张图而言,它的深拷贝即构建一张与原图结构,值均一样的图,但是其中的节点不再是原来图节点的引用。因此,为了深拷贝出整张图,我们需要知道整张图的结构以及对应节点的值。
由于题目只给了我们一个节点的引用,因此为了知道整张图的结构以及对应节点的值,我们需要从给定的节点出发,进行「图的遍历」,并在遍历的过程中完成图的深拷贝。
为了避免在深拷贝时陷入死循环,我们需要理解图的结构。对于一张无向图,任何给定的无向边都可以表示为两个有向边,即如果节点 A 和节点 B 之间存在无向边,则表示该图具有从节点 A 到节点 B 的有向边和从节点 B 到节点 A 的有向边。
为了防止多次遍历同一个节点,陷入死循环,我们需要用一种数据结构记录已经被克隆过的节点
算法
- 使用一个哈希表存储所有已被访问和克隆的节点。哈希表中的 key 是原始图中的节点,value 是克隆图中的对应节点。
- 从给定节点开始遍历图。如果某个节点已经被访问过,则返回其克隆图中的对应节点。
- 如果当前访问的节点不在哈希表中,则创建它的克隆节点并存储在哈希表中。注意:在进入递归之前,必须先创建克隆节点并保存在哈希表中。如果不保证这种顺序,可能会在递归中再次遇到同一个节点,再次遍历该节点时,陷入死循环。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> neighbors;
public Node() {
val = 0;
neighbors = new ArrayList<Node>();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList<Node>();
}
public Node(int _val, ArrayList<Node> _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
class Solution {
// key:原始图中的节点 value:克隆图中的节点
private Map<Node, Node> visited = new HashMap<>();
// 返回拷贝后的图中的 node 节点
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
if (visited.containsKey(node)) {
return visited.get(node);
}
// 克隆当前节点
Node cloneNode = new Node(node.val, new ArrayList<>());
visited.put(node, cloneNode);
// 遍历该节点的邻居并更新克隆节点的邻居列表
List<Node> neighbors = node.neighbors;
for (Node neighbor : neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}
# BFS
class Solution {
// key:原始图中的节点 value:克隆图中的节点
private Map<Node, Node> visited = new HashMap<>();
// 返回拷贝后的图中的 node 节点
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(node);
// 克隆第一个节点
Node cloneNode = new Node(node.val, new ArrayList<>());
visited.put(node, cloneNode);
while (!queue.isEmpty()) {
Node cur = queue.poll();
// 遍历当前节点的邻居并更新克隆节点的邻居列表
List<Node> neighbors = cur.neighbors;
for (Node neighbor : neighbors) {
if (!visited.containsKey(neighbor)) {
queue.offer(neighbor);
// 更新 visited
Node neighborCloneNode = new Node(neighbor.val, new ArrayList<>());
visited.put(neighbor, neighborCloneNode);
}
// 更新当前克隆节点的克隆邻居列表
visited.get(cur).neighbors.add(visited.get(neighbor));
}
}
return cloneNode;
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10