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