Clone a graph

Problem Description

Given an undirected graph write a function that returns a CLONE of that graph, example of an undirected graph:

1  ———-  2

|            /

|      /

3

Each node has a label and a list of neighbors (represented as an ArrayList).

Solution code


map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>(); //This map is gonna be used to check if a node has been already created,

//we use the original node as a key and the clone node as the value.

UndirectedGraphNode clone(UndirectedGraphNode node)
{
    if(map.containsKey(node)) //if the current node has been already cloned then just return the cloned node
        return map.get(node);

    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);  // create the clone node
    map.put(node, newNode); // put the clone into the map

    ArrayList<UndirectedGraphNode> nei = new ArrayList<UndirectedGraphNode>(); //create a new arraylist of neighbors for the new node

// loop through the neighbors of the original node and call our function recursively to build the new list of neighbors
    for(UndirectedGraphNode n : node.neighbors)
        nei.add(clone(n));

    newNode.neighbors = nei;
    return newNode;
}

Explanation:

It is basically a DFS traversal (http://en.wikipedia.org/wiki/Depth-first_search),  the clone function is called for every node and it returns the new cloned node with it’s corresponding list of neighbors, the key part here is that we need to keep track of those nodes that we have already cloned to avoid infinite loops, this is done with the HasMap.