Breadth First Search (BFS)
Example: 1
BFS: [0, 1, 2, 3, 4]
Example: 2
BFS: [1, 2, 4, 3, 5, 9, 8, 6, 7]
Real-World Example
BFS: [Mussoorie, Dehradun, Chandigarh, , Delhi, Agra, Jaipur]
This solution is also considered valid.
BFS: [Mussoorie, Dehradun, Chandigarh, , Delhi, Jaipur, Agra]
We implement Breadth-First Search (BFS) using a queue data structure
Start by choosing a source node(the node from where you want to begin the traversal).Create a visited array or setto keep track of nodes you have already visited.Add the starting node to the queueand mark it as visited.- While the queue is not empty:
- Remove (poll) one node from the front of the queue.
- Check all adjacent (neighbouring) nodes of this node.
- For each adjacent node:
- If it is not visited, then:
- Mark it as visited.
- Add it to the queue.
- If it is not visited, then:
- Repeat this process until the queue becomes empty.
Problem Statement:
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List neighbors;
}
Test case format:
For simplicity, each node’s value is the same as the node’s index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.
An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example 1:
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph. 1st node (val = 1)’s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)’s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)’s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)’s neighbors are 1st node (val = 1) and 3rd node (val = 3).
Example 2:
Input: adjList = [[]]
Output: [[]]
Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Example 3:
Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.
Constraints
- The number of nodes in the graph is in the range [0, 100].
1 <= Node.val <= 100Node.valis unique for each node.- There are no repeated edges and no self-loops in the graph.
- The Graph is connected and all nodes can be visited starting from the given node.
Approach
- If the input node is NULL → return NULL.
- Create the clone of the starting node and insert it into the map.
- Use a queue (BFS):
- Push the original root node.
- While the queue is not empty:
- Pop one node curr.
- For each neighbor n of curr:
- If n is not cloned yet:
- Create a clone of n.
- Add it to the map.
- Push n into the queue.
- Add the cloned neighbor to the neighbor list of the current cloned node.
- If n is not cloned yet:
- Return the cloned root from the map.
var cloneGraph = function(root) {
if (!root) return null;
const q = [root];
const visited = new Map();
const cloneRoot = new Node(root.val);
visited.set(root, cloneRoot);
while (q.length) {
const curr = q.shift();
const cloneCurr = visited.get(curr);
for (const n of curr.neighbors) {
if (!visited.has(n)) {
visited.set(n, new Node(n.val));
q.push(n);
}
cloneCurr.neighbors.push(visited.get(n));
}
}
return cloneRoot;
};
from collections import deque
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node: 'Node') -> 'Node':
if not node:
return None
visited = {}
q = deque([node])
cloneRoot = Node(node.val)
visited[node] = cloneRoot
while q:
curr = q.popleft()
cloneCurr = visited[curr]
for n in curr.neighbors:
if n not in visited:
visited[n] = Node(n.val)
q.append(n)
cloneCurr.neighbors.append(visited[n])
return cloneRoot
import java.util.*;
class Node {
public int val;
public List neighbors;
public Node() { val = 0; neighbors = new ArrayList(); }
public Node(int _val) { val = _val; neighbors = new ArrayList(); }
public Node(int _val, ArrayList _neighbors) { val = _val; neighbors = _neighbors; }
}
public class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map visited = new HashMap<>();
Queue q = new LinkedList<>();
Node cloneRoot = new Node(node.val);
visited.put(node, cloneRoot);
q.add(node);
while (!q.isEmpty()) {
Node curr = q.poll();
Node cloneCurr = visited.get(curr);
for (Node n : curr.neighbors) {
if (!visited.containsKey(n)) {
visited.put(n, new Node(n.val));
q.add(n);
}
cloneCurr.neighbors.add(visited.get(n));
}
}
return cloneRoot;
}
}
#include <vector>
#include <queue>
#include <nordered_map>
using namespace std;
class Node {
public:
int val;
vector neighbors;
Node() : val(0) {}
Node(int _val) : val(_val) {}
Node(int _val, vector _neighbors) : val(_val), neighbors(_neighbors) {}
};
Node* cloneGraph(Node* node) {
if (!node) return nullptr;
unordered_map visited;
queue q;
Node* cloneRoot = new Node(node->val);
visited[node] = cloneRoot;
q.push(node);
while (!q.empty()) {
Node* curr = q.front(); q.pop();
Node* cloneCurr = visited[curr];
for (Node* n : curr->neighbors) {
if (visited.find(n) == visited.end()) {
visited[n] = new Node(n->val);
q.push(n);
}
cloneCurr->neighbors.push_back(visited[n]);
}
}
return cloneRoot;
}
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int val;
struct Node** neighbors;
int neighborsCount;
} Node;
/********** Create a new node **********/
Node* createNode(int val) {
Node* n = (Node*)malloc(sizeof(Node));
n->val = val;
n->neighbors = NULL;
n->neighborsCount = 0;
return n;
}
void addNeighbor(Node* node, Node* neigh) {
node->neighbors = realloc(node->neighbors,
sizeof(Node*) * (node->neighborsCount + 1));
node->neighbors[node->neighborsCount++] = neigh;
}
Node* findClone(Node** origs, Node** clones, int size, Node* key) {
for (int i = 0; i < size; i++) {
if (origs[i] == key) {
return clones[i];
}
}
return NULL;
}
void addMapping(Node*** origs, Node*** clones, int* size,
Node* orig, Node* clone) {
int newSize = *size + 1;
*origs = realloc(*origs, newSize * sizeof(Node*));
*clones = realloc(*clones, newSize * sizeof(Node*));
(*origs)[*size] = orig;
(*clones)[*size] = clone;
*size = newSize;
}
Node* cloneGraph(Node* node) {
if (!node) return NULL;
// visited map arrays
Node** origs = NULL;
Node** clones = NULL;
int mapSize = 0;
// BFS queue
int capacity = 64;
Node** queue = malloc(sizeof(Node*) * capacity);
int head = 0, tail = 0;
// clone the root
Node* cloneRoot = createNode(node->val);
addMapping(&origs, &clones, &mapSize, node, cloneRoot);
queue[tail++] = node;
while (head < tail) {
Node* curr = queue[head++];
Node* cloneCurr = findClone(origs, clones, mapSize, curr);
for (int i = 0; i < curr->neighborsCount; i++) {
Node* neigh = curr->neighbors[i];
Node* cloneNeigh = findClone(origs, clones, mapSize, neigh);
// if not cloned yet, clone it + enqueue
if (!cloneNeigh) {
cloneNeigh = createNode(neigh->val);
addMapping(&origs, &clones, &mapSize, neigh, cloneNeigh);
if (tail == capacity) {
capacity *= 2;
queue = realloc(queue, sizeof(Node*) * capacity);
}
queue[tail++] = neigh;
}
// link clone
addNeighbor(cloneCurr, cloneNeigh);
}
}
free(queue);
free(origs);
free(clones);
return cloneRoot;
}
using System.Collections.Generic;
public class Node {
public int val;
public IList neighbors;
public Node() { val = 0; neighbors = new List(); }
public Node(int _val) { val = _val; neighbors = new List(); }
public Node(int _val, IList _neighbors) { val = _val; neighbors = _neighbors; }
}
public class Solution {
public Node CloneGraph(Node node) {
if (node == null) return null;
var visited = new Dictionary();
var q = new Queue();
Node cloneRoot = new Node(node.val);
visited[node] = cloneRoot;
q.Enqueue(node);
while (q.Count > 0) {
var curr = q.Dequeue();
var cloneCurr = visited[curr];
foreach (var n in curr.neighbors) {
if (!visited.ContainsKey(n)) {
visited[n] = new Node(n.val);
q.Enqueue(n);
}
cloneCurr.neighbors.Add(visited[n]);
}
}
return cloneRoot;
}
}
