Learn Breadth First Search Graph Traversal with Clone Graph

Problem Statement

class Node {
public int val;
public List<Node> neighbors;
}

Understanding the Problem

High Level Algorithm

  1. A Queue to put our nodes into. A queue follows the first in, first out policy, which we will later see allow us to make a BFS algorithm by processing our neighboring nodes first. This is in contrast to using a Stack, which follows a first in, last out policy which is used for DFS.
  2. A visited Set to keep track of the nodes that we visited so that we won’t explore them again, which is especially important as graphs can form a cycle and our algorithm can run forever.
  1. Put the given starting node in queue and visited set
  2. Iterating through the queue is emptied
  3. Pop a node from the queue, iterate through its children and add them to the visited set and queue if we haven’t seen them before.
  • Remove Node 1 from the queue and process its neighbor: Node 2 and Node 4.
  • Since we haven’t seen either of these nodes before, we will add them into our queue and our set.
  • We remove Node 2 from the queue and process its neighbors: Node 1 and Node 3.
  • Since Node 1 is in our visited set, we don’t want to revisit it again however we will add Node 3 into our visited set and queue.
  • Process Node 4 and its neighbors Node 1 and Node 3.
  • Both neighbors are in the visited set, so we won’t put them in the queue.
  • Remove Node 3 from queue and then look at its neighbors: Node 2 and Node 4.
  • Both are in the visited set so we won’t do anything.

Adapting the algorithm to the problem

Runtime and Space Complexity

Runtime

Space Complexity

Implementation

class Solution {
public Node cloneGraph(Node node) {
if (node == null) {
return null;
}
Queue<Node> queue = new LinkedList();
Map<Integer, Node> cloneMap = new HashMap();
queue.add(node);
cloneMap.put(node.val, new Node(node.val));

while (!queue.isEmpty()) {
Node cur = queue.remove();
Node clone = cloneMap.getOrDefault(cur.val, new Node(cur.val));
cloneMap.put(cur.val, clone);
for (Node child : cur.neighbors) {
Node childClone = cloneMap.getOrDefault(child.val, new Node(child.val));
clone.neighbors.add(childClone);
if (!cloneMap.containsKey(child.val)) {
queue.add(child);
}
cloneMap.put(child.val, childClone);
}
}
return cloneMap.get(node.val);
}
}

Conclusion

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Josh Chang

Josh Chang

Software Engineer by day, side hustler wannabee by night! https://leetdev.io