# Java BFS, DFS iterative, DFS recursion 3 solutions

• It is a good question to review the three graph traversal methods.

1. BFS

`````` public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}

HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
UndirectedGraphNode root = new UndirectedGraphNode(node.label);
map.put(node, root);
queue.offer(node);

while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
UndirectedGraphNode cur = queue.poll();
for (UndirectedGraphNode neighbor : cur.neighbors) {
UndirectedGraphNode newNeighbor = map.get(neighbor);
if (!map.containsKey(neighbor)) {
newNeighbor = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, newNeighbor);
queue.offer(neighbor);
}

}
}
}

return root;
}
}
``````
2. DFS - recursion

``````    public class Solution {
//dfs recursion
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
helper(map, node);
return map.get(node);
}

private void helper(HashMap<UndirectedGraphNode, UndirectedGraphNode> map,
UndirectedGraphNode node) {
if (node == null || map.containsKey(node)) {
return;
}

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

for (UndirectedGraphNode neighbor : node.neighbors) {
helper(map, neighbor);
}
}
}
``````
1. DFS - iterative

`````` public class Solution {
//dfs iterative
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}

HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>();
Stack<UndirectedGraphNode> stack = new Stack<>();
UndirectedGraphNode root = new UndirectedGraphNode(node.label);
map.put(node, root);
stack.push(node);

while (!stack.isEmpty()) {
UndirectedGraphNode cur = stack.pop();

for (UndirectedGraphNode neighbor : cur.neighbors) {
if (!map.containsKey(neighbor)) {
UndirectedGraphNode temp = new UndirectedGraphNode(neighbor.label);
map.put(neighbor, temp);
stack.push(neighbor);
}

}
}

return root;
}
}``````

• These are some good solutions, just some thoughts on BFS here because I was doing BFS.

1. it's good practice to specify the type of a generic class, i.e. `LinkedList<UndirectedGraph>().`
2. in the while loop, you don't have to have a for loop over queue because you are already checking if it's empty. And it's very error-prone to modify a list when you are iterating over it.

Hope this'll help.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.