Depth First Search (DFS)
Example: 1
DFS: [0, 1, 3, 2, 4]
Example: 2
DFS: [1, 4, 5, 6, 7, 3, 9, 8, 2]
Another Possible Solution:
DFS: [1, 2, 3, 4, 5, 6, 7, 8, 9]
Real-World Example
DFS: [Mussoorie, Dehradun, Delhi, Agra, Jaipur, Chandigarh]
We implement Depth-First Search (DFS) using a Stack data structure
- Push the start node into the stack.
- Create a visited set to track visited nodes.
- While the stack is not empty:
- Pop the top node.
- If not visited → mark visited and process it.
- Push all unvisited neighbors into the stack.
- Repeat until the stack 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
- Because there is no graph to clone.
- Create a stack and push the root node inside it: This stack helps perform DFS.
- Create a map (visited) to store already-cloned nodes:
- – Key: original node
- – Value: cloned node
- – Prevents re-cloning the same node again.
- Create the cloned version of the root node: Store it in the map.
- Start DFS: while the stack is not empty, Pop a node(
curr) from the stack. - Get the cloned node corresponding to curr
- – This is needed to attach cloned neighbors.
- Traverse each neighbor
nofcurr - If neighbor is not already cloned:
- Create its clone.
- Add it to the map.
- Push the neighbor onto the stack (so we explore it later).
- Connect the cloned nodes:
- Add
visited.get(n)to cloneCurr.neighbors
- Add
- After DFS completes, return the cloned root.
var cloneGraph = function(root) {
if (!root) return null;
const stack = [root];
const visited = new Map();
const cloneRoot = new Node(root.val);
visited.set(root, cloneRoot);
while (stack.length) {
const curr = stack.shift();
const cloneCurr = visited.get(curr);
for (const n of curr.neighbors) {
if (!visited.has(n)) {
visited.set(n, new Node(n.val));
stack.push(n);
}
cloneCurr.neighbors.push(visited.get(n));
}
}
return cloneRoot;
};
def cloneGraph(root: 'Node') -> 'Node':
if not root:
return None
stack = [root]
visited = {} # original_node -> cloned_node
cloneRoot = Node(root.val)
visited[root] = cloneRoot
while stack:
curr = stack.pop() # LIFO: iterative DFS
cloneCurr = visited[curr]
for n in curr.neighbors:
if n not in visited:
visited[n] = Node(n.val)
stack.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 root) {
if (root == null) return null;
Deque stack = new ArrayDeque<>();
Map visited = new HashMap<>();
Node cloneRoot = new Node(root.val);
visited.put(root, cloneRoot);
stack.push(root);
while (!stack.isEmpty()) {
Node curr = stack.pop(); // LIFO
Node cloneCurr = visited.get(curr);
for (Node n : curr.neighbors) {
if (!visited.containsKey(n)) {
visited.put(n, new Node(n.val));
stack.push(n);
}
cloneCurr.neighbors.add(visited.get(n));
}
}
return cloneRoot;
}
}
#include <vector>
#include <stack>
#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* root) {
if (!root) return nullptr;
unordered_map visited; // original -> clone
stack st;
Node* cloneRoot = new Node(root->val);
visited[root] = cloneRoot;
st.push(root);
while (!st.empty()) {
Node* curr = st.top(); st.pop(); // LIFO
Node* cloneCurr = visited[curr];
for (Node* n : curr->neighbors) {
if (visited.find(n) == visited.end()) {
visited[n] = new Node(n->val);
st.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;
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;
}
/* visited mapping using parallel arrays origs[i] -> clones[i] */
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*** origsRef, Node*** clonesRef, int* sizeRef, Node* orig, Node* clone) {
int size = *sizeRef;
*origsRef = realloc(*origsRef, (size + 1) * sizeof(Node*));
*clonesRef = realloc(*clonesRef, (size + 1) * sizeof(Node*));
(*origsRef)[size] = orig;
(*clonesRef)[size] = clone;
*sizeRef = size + 1;
}
/* iterative DFS clone */
Node* cloneGraph(Node* root) {
if (!root) return NULL;
Node** origs = NULL;
Node** clones = NULL;
int mapSize = 0;
int stackCap = 64;
Node** stack = malloc(sizeof(Node*) * stackCap);
int sp = 0; // stack pointer: push -> stack[sp++] , pop -> stack[--sp]
Node* cloneRoot = createNode(root->val);
addMapping(&origs, &clones, &mapSize, root, cloneRoot);
// push root
if (sp == stackCap) { stackCap *= 2; stack = realloc(stack, sizeof(Node*) * stackCap); }
stack[sp++] = root;
while (sp > 0) {
Node* curr = stack[--sp]; // pop (LIFO)
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 (!cloneNeigh) {
cloneNeigh = createNode(neigh->val);
addMapping(&origs, &clones, &mapSize, neigh, cloneNeigh);
if (sp == stackCap) {
stackCap *= 2;
stack = realloc(stack, sizeof(Node*) * stackCap);
}
stack[sp++] = neigh; // push neighbor to stack for DFS
}
addNeighbor(cloneCurr, cloneNeigh);
}
}
free(stack);
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 root) {
if (root == null) return null;
var stack = new Stack();
var visited = new Dictionary();
var cloneRoot = new Node(root.val);
visited[root] = cloneRoot;
stack.Push(root);
while (stack.Count > 0) {
var curr = stack.Pop(); // LIFO
var cloneCurr = visited[curr];
foreach (var n in curr.neighbors) {
if (!visited.ContainsKey(n)) {
visited[n] = new Node(n.val);
stack.Push(n);
}
cloneCurr.neighbors.Add(visited[n]);
}
}
return cloneRoot;
}
}
