OJ练习第151题——克隆图

克隆图

力扣链接：133. 克隆图

题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

示例

分析

对于一张图而言，它的深拷贝即构建一张与原图结构，值均一样的图，但是其中的节点不再是原来图节点的引用。因此，为了深拷贝出整张图，我们需要知道整张图的结构以及对应节点的值。

由于题目只给了我们一个节点的引用，因此为了知道整张图的结构以及对应节点的值，我们需要从给定的节点出发，进行「图的遍历」，并在遍历的过程中完成图的深拷贝。

为了防止多次遍历同一个节点，陷入死循环，我们需要用一种数据结构记录已经被克隆过的节点。

深度优先搜索

class Solution {private HashMap<Node, Node> visited = new HashMap<>();public Node cloneGraph(Node node) {if(node == null) return node;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;}
}

广度优先搜索

class Solution {public Node cloneGraph(Node node) {if(node == null) return node;HashMap<Node, Node> visited = new HashMap<>();LinkedList<Node> queue = new LinkedList<Node>();queue.add(node);visited.put(node, new Node(node.val, new ArrayList()));while(!queue.isEmpty()) {Node n = queue.remove();for(Node neighbor : n.neighbors) {if(!visited.containsKey(neighbor)) {visited.put(neighbor, new Node(neighbor.val, new ArrayList()));queue.add(neighbor);}visited.get(n).neighbors.add(visited.get(neighbor));}}return visited.get(node);}
}