Clone Graph
- 2 min read
- Graph
- LC-Medium
3 years ago
Solution
- Just do a Depth-first Search while maintaining a hashmap where key is the old node and value is the new node
- Recur for neighbors as well. Check the code, it should be very simple to understand
- Hashmap is needed because there should be only one instance of any node. When doing traversal, we will at some point meet the same node again, and instead of creating a new node which is wrong, we use the reference of the already created node. This is akin to using the visited set when doing a typical graph traversal.
| Time | Space | Explanation |
|---|---|---|
O(m + n) | O(n) | n = number of nodes, m = number of edges |
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
refs = {}
def clone(node):
if node not in refs:
copy = Node(node.val)
refs[node] = copy
for nbr in node.neighbors:
copy.neighbors.append(clone(nbr))
return refs[node]
return clone(node) if node else None
Alternate solution that did not work
I don't know why this didn't work. It uses the same concept as Copy List with Random Pointer. I even printed the neighbours of each copied node inside the refs dictionary. It seemed correct. But it did not pass the test cases.
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if node is None:
return None
# First DFS, Create references of old node to new node
refs = {}
vis = set()
def dfs1(node):
if node not in vis:
vis.add(node)
refs[node] = Node(node.val)
for nbr in node.neighbors:
dfs1(nbr)
# Second DFS, assign neighbors to copies of node
vis = set()
def dfs2(node):
if node not in vis:
vis.add(node)
refs[node].neighbors = [refs[nbr] for nbr in node.neighbors]
for nbr in node.neighbors:
dfs2(nbr)
dfs1(node)
dfs2(node)
return refs[node]