If you have ever played around with Algorithms & Data Structures, then you most likely have heard of Leetcode.com, which contains a number of famous (or infamous) of technical questions. One of my favorite in there is the graph clone question, which can be shortly stated as:

```
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
```

Like most algorithms & data structures problems, there are usually many variants to solving this problem, but here I will go through the solution that is most typically reported. To begin, it is generally good form to define a `Node`

class:

1
2
3
4
5
6
7
8

class Node:
'''
Define a node class for our undirected graph
'''
def __init__(self, node_label, node_neighbors=[]):
self.label = node_label
self.neighbors = node_neighbors

You can test the `Node`

class in your Python interpreter as below (although this would never be considered a test per-se if we are talking in engineering terms!)

1
2
3
4
5
6

>>> test_node = Node('test')
>>> print test_node.label
test
>>> print test_node.neighbors
[]

Finally, we can define the `Solution`

class, which will allow us to clone any graph given that we are provided at least one of its node:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
'''
Clone undirected graph
'''
def cloneGraph(self, node):
nodeMap = {}
return self.cloneNode(node, nodeMap)
def cloneNode(self, node, nodeMap):
if node == None:
return None
if node.label in nodeMap:
return nodeMap[node.label]
newNode = Node(node.label)
nodeMap[node.label] = newNode
for neighbor in node.neighbors:
newNode.neighbors.append(self.cloneNode(neighbor, nodeMap))
return newNode

So what does the code above do? Quite clearly, the `cloneGraph`

function in lines 5-7 takes as input a node belonging to the graph we wish to clone, and then initializes a hash map (or dictionnary if we are talking in Python terms). Finally it invokes the `cloneNode`

function that is defined in lines 9-18. First, the `cloneNode`

function checks for an empty node and if this statement is met returns a `None`

value. The next step (lines 12-13) is to check whether the input node is already in `nodeMap`

, which would indicate it has already been processed. If this condition is met, then we simply return label of the node (for reasons that will become clear in the next paragraph).

At this point, we get to the meaty part of our solution. Line 14 with the statement `newNode = Node(node.label)`

initiates a new node with the same label as the input node and no neighbors (the default for the `Node`

class). Next, we add the newly created `newNode`

object to the hash map `nodeMap`

. Finally, we iterate through all known neighbors of the input node, and recursively append the results of calling `cloneNode`

to each of those neighbors. In doing so, nodes already cloned in `nodeMap`

will simply be appended to the neighbor list of `newNode`

(because of the conditional statement in lines 12-13), while all others will also be recursively added to the `nodeMap`

hash map. This will have the direct effect of cloning the entire original graph to the `nodeMap`

hashmap! And we are done!