Depth First Simple Java Solution

• ``````public class Solution {
private HashMap<Integer, UndirectedGraphNode> map = new HashMap<>();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return clone(node);
}

private UndirectedGraphNode clone(UndirectedGraphNode node) {
if (node == null) return null;

if (map.containsKey(node.label)) {
return map.get(node.label);
}
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(clone.label, clone);
for (UndirectedGraphNode neighbor : node.neighbors) {
}
return clone;
}
}``````

• can this approach handle the case that there are nodes having the same label value in a cycle?. I think it might be better to use the HashMap<UndirectedGraphNode, UndirectedGraphNode>

• Very good solution. It can be written inside just one method as well.

• As @san89kalp said, it can be written in just one method.

``````public HashMap<Integer, UndirectedGraphNode> map = new HashMap();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
if (map.containsKey(node.label))
return map.get(node.label);
UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);
map.put(cloned.label, cloned);
for(UndirectedGraphNode neighbor: node.neighbors){
}
return cloned;
}``````

• @ chenw2000, by putting this line `map.put(clone.label, clone);` before for loop makes sure cycle can be detected.

• I think it is better not to use global hashmap in practice. Here is my more general solution.

``````public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
HashMap<Integer,UndirectedGraphNode> map = new HashMap<Integer,UndirectedGraphNode>();
return dfs(node,map);
}
private UndirectedGraphNode dfs(UndirectedGraphNode node, HashMap<Integer,UndirectedGraphNode> map) {
if (node == null) return null;
if (map.containsKey(node.label)) {
return map.get(node.label);
} else {
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(node.label,clone);
for (int i = 0; i < node.neighbors.size(); i++) {
}
return clone;
}
}``````

• clone is key word, we'd better not define key word as variable.

• I think we can get rid of the helper function because the map is global :) https://leetcode.com/discuss/91813/without-helper-function-java-dfs-simple-solution

• Another implementation based on your idea, just a few changes. Map is defined as local variable instead of global, used Map<> instead of HashMap<> to be more generic.

``````public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
Map<Integer, UndirectedGraphNode> map = new HashMap<>();
return dfs(node, map);
}

private UndirectedGraphNode dfs(UndirectedGraphNode node, Map<Integer, UndirectedGraphNode> map) {
if(node == null) {
return null;
}
if(map.containsKey(node.label)) {
return map.get(node.label);
}
UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
map.put(node.label, clone);
for(UndirectedGraphNode next : node.neighbors) {
}
return clone;
}``````

• This post is deleted!

• This post is deleted!

• As @keran.yang.5 said, by this way, you cannot recursively invoke the function clone().

• Nice! Here's another quick variation, saves a few recursive calls:

``````public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
return cloneGraph(node, new HashMap<UndirectedGraphNode, UndirectedGraphNode>());
}

private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap) {
if (node == null) return null;
UndirectedGraphNode cloned = new UndirectedGraphNode(node.label);
cloneMap.put(node, cloned); // visited = true;
for(UndirectedGraphNode neighbor: node.neighbors){
if (cloneMap.containsKey(neighbor)) { // if we have already explored this vertex grab its clone from map
} else { // explore unvisited vertex
}
}
return cloned;
}
}
``````

• I want to know if the label is key word? if not, should use HashMap<UndirectedGraphNode,UndirectedGraphNode>

• This post is deleted!

• @levani Same idea as yours by passing Map as method argument. Since "Nodes are labeled uniquely", I choose label as key. Thanks for sharing!

``````    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
return dfs(node, new HashMap<>());
}

private UndirectedGraphNode dfs(UndirectedGraphNode node,
Map<Integer,UndirectedGraphNode> copies) {
if (copies.containsKey(node.label)) return copies.get(node.label);

UndirectedGraphNode cpy = new UndirectedGraphNode(node.label);
copies.put(cpy.label, cpy);

for (UndirectedGraphNode n : node.neighbors)
return cpy;
}
``````

• @levani I have the same idea. It is easy to read.
my code

• @levani said in Depth First Simple Java Solution:

HashMap<UndirectedGraphNode, UndirectedGraphNode>()

I vote the method with HashMap<UndirectedGraphNode, UndirectedGraphNode>() since it can handle the situation that two nodes with the same label value.

• Nice solution!

My slight variations:

• Only check for null in the initial call
• Do not use global hash map
• map node to cloned node instead of label to cloned node in case of duplicate labels
``````public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;
return cloneGraph(node, new HashMap<>());
}

private UndirectedGraphNode cloneGraph(UndirectedGraphNode node, Map<UndirectedGraphNode, UndirectedGraphNode> visited) {
if (visited.containsKey(node)) return visited.get(node);

UndirectedGraphNode clone = new UndirectedGraphNode(node.label);

visited.put(node, clone);

for (UndirectedGraphNode neighbor : node.neighbors)

return clone;
}
``````

• This question is the same as `copy list with random pointer`.

``````Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap();
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) return null;

if (map.containsKey(node)) return map.get(node);

UndirectedGraphNode myNode = new UndirectedGraphNode(node.label);
map.put(node, myNode);

for (UndirectedGraphNode n : node.neighbors) {