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]
2 [3,4]
3 [4]
4 [1]
```

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)`