克隆圖
力扣鏈接：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);}
}
