Clone Graph (Java)

LeetCode

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

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Solution: DFS traverse all nodes, meanwhile use HashMap to record the node which has been cloned. use label as key and the new created node as value

	Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
	OJ's undirected graph serialization:
	Nodes are labeled uniquely.
	We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
	As an example, consider the serialized graph {0,1,2#1,2#2,2}.
	The graph has a total of three nodes, and therefore contains three parts as separated by #.
	First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
	Second node is labeled as 1. Connect node 1 to node 2.
	Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
	Visually, the graph looks like the following:
	1
	/ \
	/ \
	0 --- 2
	/ \
	\_/
	/**
	* Definition for undirected graph.
	* class UndirectedGraphNode {
	* int label;
	* ArrayList<UndirectedGraphNode> neighbors;
	* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
	* };
	*/
	public class Solution {
	public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
	if (node==null){
	return null;
	}
	HashMap<Integer, UndirectedGraphNode> checker=new HashMap<Integer, UndirectedGraphNode>();
	return clone(node, checker);
	}
	private UndirectedGraphNode clone (UndirectedGraphNode node, HashMap<Integer, UndirectedGraphNode> checker){
	if (checker.containsKey(node.label)){
	return checker.get(node.label);
	}
	UndirectedGraphNode newNode=new UndirectedGraphNode(node.label);
	checker.put(newNode.label,newNode);
	for (UndirectedGraphNode tempNode: node.neighbors){
	newNode.neighbors.add(clone(tempNode, checker));
	}
	return newNode;
	}
	}

view raw CloneGraph.java hosted with ❤ by GitHub