Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
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 node0to both nodes1and2. - Second node is labeled as
1. Connect node1to node2. - Third node is labeled as
2. Connect node2to node2(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1 / \ / \ 0 --- 2 / \ \_/
对图的遍历就是两个经典的方法DFS和BFS，和思路一样，用一个HashMap记录原图节点和复制图节点间的对应关系，以防止重复建立节点，key存原始值，value存copy的值，用DFS,BFS方法遍历帮助拷贝neighbors的值。和那题的不同在于遍历原图相对比linked list的情况复杂一点。可以用BFS或DFS来遍历原图。而HashMap本身除了记录对应关系外，还有记录原图中每个节点是否已经被visit的功能。
Java: DFS
public class Solution { private HashMap map = new HashMap<>(); public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { return clone(node); } private UndirectedGraphNode clone(UndirectedGraphNode node) { if (node == null) return null; if (map.containsKey(node.label)) { return map.get(node.label); } UndirectedGraphNode clone = new UndirectedGraphNode(node.label); map.put(clone.label, clone); for (UndirectedGraphNode neighbor : node.neighbors) { clone.neighbors.add(clone(neighbor)); } return clone; }} Java: BFS
/** * 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; }} Java: BFS
/** * 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; }} Python: DFS
class UndirectedGraphNode: def __init__(self, x): self.label = x self.neighbors = []class Solution: def cloneGraph(self, node): def dfs(input, map): if input in map: return map[input] output = UndirectedGraphNode(input.label) map[input] = output for neighbor in input.neighbors: output.neighbors.append(dfs(neighbor, map)) return output if node == None: return None return dfs(node, {}) Python: BFS
class UndirectedGraphNode: def __init__(self, x): self.label = x self.neighbors = []class Solution: # @param node, a undirected graph node # @return a undirected graph node def cloneGraph(self, node): if node is None: return None cloned_node = UndirectedGraphNode(node.label) cloned, queue = {node:cloned_node}, [node] while queue: current = queue.pop() for neighbor in current.neighbors: if neighbor not in cloned: queue.append(neighbor) cloned_neighbor = UndirectedGraphNode(neighbor.label) cloned[neighbor] = cloned_neighbor cloned[current].neighbors.append(cloned[neighbor]) return cloned[node] C++：DFS
class Solution {public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(!node) return NULL; unordered_map ht; stack s; s.push(node); ht[node] = new UndirectedGraphNode(node->label); while(!s.empty()) { UndirectedGraphNode *p1 = s.top(), *p2 = ht[p1]; s.pop(); for(int i=0; i neighbors.size(); i++) { UndirectedGraphNode *nb = p1->neighbors[i]; if(ht.count(nb)) { p2->neighbors.push_back(ht[nb]); } else { UndirectedGraphNode *temp = new UndirectedGraphNode(nb->label); p2->neighbors.push_back(temp); ht[nb] = temp; s.push(nb); } } } return ht[node]; }}; C++: BFS
class Solution {public: UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { if(!node) return NULL; UndirectedGraphNode *p1 = node; UndirectedGraphNode *p2 = new UndirectedGraphNode(node->label); unordered_map ht; queue q; q.push(node); ht[node] = p2; while(!q.empty()) { p1 = q.front(); p2 = ht[p1]; q.pop(); for(int i=0; i neighbors.size(); i++) { UndirectedGraphNode *nb = p1->neighbors[i]; if(ht.count(nb)) { p2->neighbors.push_back(ht[nb]); } else { UndirectedGraphNode *temp = new UndirectedGraphNode(nb->label); p2->neighbors.push_back(temp); ht[nb] = temp; q.push(nb); } } } return ht[node]; }};
相似题目：