I am trying to clone a graph using DFS
in Java
iteratively
, but on compiling it keeps on showing NullPointerException
. I know the code using recursion
is uch simpler, but wanted to try out in iterative
way.
The code is shown below:
/**
* Definition for undirected graph.
* class UndirectedGraphNode {
* int label;
* List<UndirectedGraphNode> neighbors;
* UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node==null) return null;
Map<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<>();
Stack<UndirectedGraphNode> st = new Stack<>();
st.push(node);
while(!st.isEmpty())
{
UndirectedGraphNode n = st.pop();
UndirectedGraphNode copy = null;
if(!hm.containsKey(n)) //if n is cloned before, no need to clone it again
{
copy = new UndirectedGraphNode(n.label); //clone parent
hm.put(n, copy);
}
else
copy = hm.get(n);
for(UndirectedGraphNode neighbor: n.neighbors)
{
if(!hm.containsKey(neighbor))
{
UndirectedGraphNode copy_neighbor = new UndirectedGraphNode(neighbor.label);
copy.neighbors.add(copy_neighbor); //clone child.
hm.put(neighbor, copy_neighbor);
st.push(neighbor);
}else
copy.neighbors.add(hm.get(neighbor));//this handles parent node as well.
}
}
return hm.get(node);
}
Here, what I am tryig to do is get a node from the graph and traverse to it's next connected node or as in this case neighbor
.
The NullPointerException
is being shown in this line :
copy.neighbors.add(copy_neighbor);
StackTrace
java.lang.NullPointerException
at line 55, Solution.cloneGraph
at line 102, __Driver__.main