# Clone Graph ## Question > Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a`label` (`int`) and a list (`List[UndirectedGraphNode]`) of its`neighbors`. There is an edge between the given node and each of the nodes in its neighbors. Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors. How we serialize an undirected graph: Nodes are labeled uniquely. We use `#` as a separator for each node, and `,` as a separator for node label and each neighbor of the node. As an example, consider the serialized graph `{0,1,2#1,2#2,2}.` The graph has a total of three nodes, and therefore contains three parts as separated by #. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.\ Second node is labeled as 1. Connect node 1 to node 2.\ Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle. Visually, the graph looks like the following: ```java 1 / \ / \ 0 --- 2 / \ \_/ ``` Have you met this question in a real interview? Yes **Example**\ return a deep copied graph. **Tags**\ Breadth First Search Facebook ## Analysis 本题是Graph相关的基础问题，图的遍历主要有两种方法：BFS，DFS，也就是广度优先搜索和深度优先搜索。 **Breadth-first Search** > Wikipedia:\ > “In graph theory, breadth-first search (BFS) is a strategy for searching in a graph\ > when search is limited to essentially two operations: (a) visit and\ > inspect a node of a graph; (b) gain access to visit the nodes that\ > neighbor the currently visited node. The BFS begins at a root node and\ > inspects all the neighboring nodes. Then for each of those neighbor\ > nodes in turn, it inspects their neighbor nodes which were unvisited,\ > and so on. Compare BFS with the equivalent, but more memory-efficient\ > Iterative deepening depth-first search and contrast with depth-first search.” 这是一种对图的遍历方法，对于一个节点来说先把所有neighbors都检查一遍，再从\ 第一个neighbor开始，循环往复。 由于BFS的这个特质，BFS可以帮助寻找最短路径。 通常BFS用queue+循环实现。 **Depth-first Search** > Wikipedia:\ > “Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.\ > One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible\ > along each branch before backtracking.” 通常来说简便的DFS写法是用递归，如果非递归的话就是栈套迭代，思想是一样的。 思路1：使用BFS，先将头节点入queue，每一次queue出列一个node，然后检查这个node的所有的neighbors，如果没visited过，就入队，并更新neighbor。 思路2：使用DFS，可以分为迭代和循环两种方式，后者需要利用stack。 ## Solution ### BFS - breadth first search, non-recursive ```java /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); } * }; */ public class Solution { /** * @param node: A undirected graph node * @return: A undirected graph node */ public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } HashMap hm = new HashMap(); LinkedList queue = new LinkedList(); UndirectedGraphNode head = new UndirectedGraphNode(node.label); hm.put(node, head); queue.add(node); while (!queue.isEmpty()) { UndirectedGraphNode currentNode = queue.remove(); for (UndirectedGraphNode neighbor : currentNode.neighbors) { if (!hm.containsKey(neighbor)) { queue.add(neighbor); UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label); hm.put(neighbor, newNeighbor); } hm.get(currentNode).neighbors.add(hm.get(neighbor)); } } return head; } } ``` ### DFS - depth first search, non-recursive ```java /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * ArrayList neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList(); } * }; */ public class Solution { /** * @param node: A undirected graph node * @return: A undirected graph node */ public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node == null) return null; HashMap hm = new HashMap(); LinkedList stack = new LinkedList(); UndirectedGraphNode head = new UndirectedGraphNode(node.label); hm.put(node, head); stack.push(node); while(!stack.isEmpty()){ UndirectedGraphNode curnode = stack.pop(); for(UndirectedGraphNode aneighbor: curnode.neighbors){//check each neighbor if(!hm.containsKey(aneighbor)){//if not visited,then push to stack stack.push(aneighbor); UndirectedGraphNode newneighbor = new UndirectedGraphNode(aneighbor.label); hm.put(aneighbor, newneighbor); } hm.get(curnode).neighbors.add(hm.get(aneighbor)); } } return head; } } ``` ### DFS Recursive ```java public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } return cloneGraph(node, new HashMap<>()); } private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map cloneMap) { UndirectedGraphNode clone = new UndirectedGraphNode(node.label); cloneMap.put(node, clone); for (UndirectedGraphNode neighbor : node.neighbors) { UndirectedGraphNode neighborClone = cloneMap.get(neighbor); if (neighborClone != null) { clone.neighbors.add(neighborClone); } else { clone.neighbors.add(cloneGraph(neighbor, cloneMap)); } } return clone; } } ``` ## Reference * [Clone Graph leetcode java（DFS and BFS 基础）](http://www.cnblogs.com/springfor/p/3874591.html) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://aaronice.gitbook.io/lintcode/graph_search/clone_graph.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.