算法题：克隆图
图的克隆到底怎么玩？
用DFS解题
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 {
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 cloneNode = new Node(node.val, new ArrayList<>());
visited.put(node, cloneNode);
// 递归克隆所有邻居
for (Node neighbor : node.neighbors) {
cloneNode.neighbors.add(cloneGraph(neighbor));
}
return cloneNode;
}
}
visited 来存储原节点和克隆节点的映射关系，既能防止重复克隆，又能有效处理环形图。再来看BFS解法
class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
// 存储原节点到克隆节点的映射
Map<Node, Node> visited = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
// 初始化队列和映射
Node cloneNode = new Node(node.val, new ArrayList<>());
visited.put(node, cloneNode);
queue.add(node);
// BFS
while (!queue.isEmpty()) {
Node curr = queue.poll();
// 遍历当前节点的邻居
for (Node neighbor : curr.neighbors) {
if (!visited.containsKey(neighbor)) {
// 如果没被克隆，先克隆再加入队列
Node neighborClone = new Node(neighbor.val, new ArrayList<>());
visited.put(neighbor, neighborClone);
queue.add(neighbor);
}
// 添加邻居到当前节点的邻居列表
visited.get(curr).neighbors.add(visited.get(neighbor));
}
}
return cloneNode;
}
}
对编程、职场感兴趣的同学，可以链接我，微信：coder301 拉你进入“程序员交流群”。
