Zunayed Ali Morsalin Home

# Clone a connected graph

Tags: graphs

Problem statement

Given a node in a connected graph clone the entire graph included the connection details At first glance this problem seems pretty straight forward. We can just do a traversal and clone all the Nodes. While this would get us all the Nodes all the neighbor info wouldn’t be maintained. For example take a look at `Node(4)` who’s in the neighbor list for both `Node(2)` and `Node(3)`. If we just simply traverse we won’t maintain that connection between `Node(2)` and `Node(3)`. So let’s take a look at a standard dfs approach to traversing the graph.

``````def dfs(list_of_vertices):
seen = set()

for cur in list_of_vertices:
if (cur.val not in seen):
path = []
explore(cur, seen, path)
print(path)

def explore(cur, seen, path):
seen.add(cur.val)
path.add(cur.val))

for (n in cur.neighbors):
if (n not in seen):
explore(n, seen, path)
``````

Since we are know that 1. the graph is connected and 2. only given one node we can rewrite the above

``````
def explore_runner(start):
seen = set()
explore(start, seen)

def explore(start, seen):
if start in seen:
return

for n in start.neighbors:
if (n not in seen):
explore(n, seen)
``````

So to reiterate the earlier point about the connections not being minted if we just traverse let’s take a look at all the info at once.

``````node  |  neighbors
1        
2        [3,4]
3        
4        
`````` If we take a look at our explore function we see that we actually visit every neighbor of a node. We just immediately return if it’s in the seen set. What if we didn’t return `none` and return the neighbor object itself. If we did that we can assign it to the current clone of the node we are exploring. We can replace our set with a dictionary that can store the list of neighbors.

a. We look at `Node(1)` and fill in our map we then go to all of it’s neighbors
b. When traversing the neighbor we end up at `Node(2)`
c. When traversing the neighbors of `Node(2)` recurse w/`Node(3)`
d. When traversing the neighbors of `Node(3)` recurse w/`Node(4)`
d. When traversing the neighbors of `Node(4)` recurse w/`Node(1)`
e. Now at this point we have seen `Node(1)` already so we returned the actual `Node(1)` itself so we can append it to the neighbors list
f. Recurse back up the callstack since there are no more neighbors with the cloned object `Node(4)` and append it to `Node(3)` neighbor list
g. Recurse back up the callstack since there are no more neighbors with the cloned object `Node(3)` and append it to `Node(2)` neighbor list
h. When traversing the neighbors of `Node(2)` recurse w/`Node(4)`
i. Now at this point we have seen `Node(4)` already so we returned the actual `Node(4)`
j. Recurse back up the callstack since there are no more neighbors with the cloned object `Node(4)` and append it to `Node(2)` neighbor list
j. Recurse back up the callstack since there are no more neighbors with the cloned object `Node(2)` and append it to `Node(1)` neighbor list

Finally we return `Node(1)`

Putting it altogether

``````def clone_runner(node):
clone_map = {}
return clone(node, clone_map)

def clone(cur, clone_map):
if cur.val in clone_map:
return clone_map[cur.val]

cloned = Node(cur.val)
clone_map[cloned.val] = cloned

for n in cur.neighbors:
cloned_neighbor = clone(n, clone_map)
clone.neighbors.append(cloned_neighbor)

return clone
``````

The runtime complexity of those will be `O(v + e)`