Question
Formatted question description: https://leetcode.ca/all/133.html
133 Clone Graph
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 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:
1
/ \
/ \
0 --- 2
/ \
\_/
Note:
The number of nodes will be between 1 and 100.
The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
You must return the copy of the given node as a reference to the cloned graph.
@tag-graph
Algorithm
In the recursive function, it is first to check if empty, and then to see whether the current node has been cloned,
- if it exists in the HashMap, it will directly return to its mapping node.
- Otherwise, clone the current node and create a mapping in HashMap, then traverse all neihbor nodes of the current node, call the recursive function and add it to the neighbors array of the cloned node.
Same idea of HashMap for BFS solution.
Code
Java
-
import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; public class Clone_Graph { /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { // from original node, to its copy HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<>(); Set<UndirectedGraphNode> visited = new HashSet<>(); public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if (node == null) { return null; } // it can be done in either dfs or bfs // I prefer bfs, less space cost Queue<UndirectedGraphNode> q = new LinkedList<UndirectedGraphNode>(); q.offer(node); while (!q.isEmpty()) { UndirectedGraphNode currentOriginal = q.poll(); UndirectedGraphNode currentCopy = getClonedNode(currentOriginal); visited.add(currentOriginal); for (UndirectedGraphNode nb: currentOriginal.neighbors) { UndirectedGraphNode nbCopy = getClonedNode(nb); /* Input: {0,0,0} Output: {0,0,0,0,0} Expected: {0,0,0} */ // @note: if add each other, then failed by above input // so, should only add currentCopy's neighbors, and rest put in queue for next processing currentCopy.neighbors.add(nbCopy); // if (!visited.contains(nb)) { if (!visited.contains(nb) && !q.contains(nb)) { q.offer(nb); } } } return hm.get(node); } private UndirectedGraphNode getClonedNode(UndirectedGraphNode original) { UndirectedGraphNode originalCopy; if (!hm.containsKey(original)) { originalCopy = new UndirectedGraphNode(original.label); hm.put(original, originalCopy); // as long as no mapping from original to its copy, add it } else { originalCopy = hm.get(original); } return originalCopy; } } }
-
// OJ: https://leetcode.com/problems/clone-graph/ // Time: O(N) // Space: O(N) class Solution { unordered_map<Node*, Node*> m; public: Node* cloneGraph(Node* node) { if (!node) return nullptr; if (m.count(node)) return m[node]; auto cpy = new Node(node->val); m[node] = cpy; for (auto &n : node->neighbors) cpy->neighbors.push_back(cloneGraph(n)); return cpy; } };
-
# Definition for a undirected graph node # 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): graph = {} visited = set() def dfs(node, visited, graph): if not node or node.label in visited: return visited |= {node.label} if node.label not in graph: graph[node.label] = UndirectedGraphNode(node.label) newNode = graph[node.label] for nbr in node.neighbors: if nbr.label not in graph: graph[nbr.label] = UndirectedGraphNode(nbr.label) newNode.neighbors.append(graph[nbr.label]) dfs(nbr, visited, graph) return newNode return dfs(node, visited, graph)