Graph: Clone a directed graph

Question:

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

Approach: Do a breadth first search of the input graph and while cloning individual graph nodes, do check if you have already created that graph node or not. We can use a hashmap to remind ourselves if we have already created a particular graph node or not.

Here is the guts of the logic:

` public GraphNode cloneGraph(GraphNode node) { //Graph newGraph = new Graph(this.vertices); //int start = 1; Queue queue = new LinkedList(); Map<GraphNode, GraphNode> hmap = new HashMap<GraphNode, GraphNode>();

	//queue.add(this.graph.gnodes[start]);
	queue.add(node);	
	GraphNode uNew = null;
	boolean [] visited = new boolean[this.vertices+1];
	
	
	while (!queue.isEmpty()) {
		GraphNode u = queue.remove();
		visited[u.label] = true;
		if (hmap.containsKey(u)) {
			uNew = hmap.get(u);
		} else {
			uNew = new GraphNode(u.label);
			hmap.put(u, uNew);
		}
		List<GraphNode> vlist = u.neighbors;
		int size = vlist.size();
		for (int i=0; i<size; i++) {
			GraphNode v = vlist.get(i);
			if (visited[v.label]) {
				continue;
			}
			GraphNode vNew = null;
			if (!hmap.containsKey(v)) {
				vNew = new GraphNode(v.label);
				hmap.put(v, vNew);
				queue.add(v);
			} else {
				vNew = hmap.get(v);
			}
			uNew.neighbors.add(vNew);
			vNew.neighbors.add(uNew);
		}
	}
	
	
	//print the cloned graph
	System.out.println("cloned graph: ");
	for (int i=1; i<=this.vertices; i++) {
		System.out.println(hmap.get(this.graph.gnodes[i]).toString());
	}
	
	return hmap.get(node);
}

} `