Clone Graph
Problem Statement
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 node0
to both nodes1
and2
. - Second node is labeled as
1
. Connect node1
to node2
. - Third node is labeled as
2
. Connect node2
to node2
(itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
Approach
Since we have to clone the given graph, first thing to remember is each node should be cloned/copied. We cannot assign old references. A simple Breadth First traversal can be performed on the graph to create a clone. DFS can also achieve this goal but we have used BFS here.
We will also main a hash table<Label,UndirectedNode> to keep track of the copies of nodes and to take care of the cyclic graphs. The UndirectedNode in the has table is the copy/clone of the node.
A Queue (FIFO) is maintained to process each node and its neighbors sequentially.
- If the node is null, return null else go to step 2
- Do the following :
- Push the first node to the queue
- Create a copy of this node and store in the hash table<label,copy of node>
- Go through every element in the queue until it is empty and check
- If each neighbor of first node is already in the hashTable that means we have already created its copy . All we need to do is to add it as a neighbor to the first node. Also, it will not be added to the queue because it is already been processed.
- If neighbor is not in hash table,
- Add this neighbor to the queue. Since its encountered first time.
- Create a copy and store in hash table
- Add this to the neighbor list of the first node
Run Time Complexity
The Time complexity for cloning the graph is O(V+E) and thats because we shall be traversing each vertex of the graph from the Queue and then visiting each edge E atleast once.
Code
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
Map<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>();public UndirectedGraphNode cloneGraph(UndirectedGraphNode node){
if(node == null){
return null;
}queue.add(node);
UndirectedGraphNode nodeToReturn = new UndirectedGraphNode(node.label);
map.put(nodeToReturn.label,nodeToReturn);
while(queue.size() > 0){
UndirectedGraphNode head = queue.remove();
for(UndirectedGraphNode neighbor: head.neighbors){
if(map.containsKey(neighbor.label)){
map.get(head.label).neighbors.add(map.get(neighbor.label));
}else{
queue.add(neighbor);
UndirectedGraphNode neighborNodeCopy = new UndirectedGraphNode(neighbor.label);
map.put(neighbor.label,neighborNodeCopy);
map.get(head.label).neighbors.add(neighborNodeCopy);
}
}
}
return nodeToReturn;
}
}
If you like it share, you can follow me on Twitter or share it with people you care!