Problem Statement
Given an undirected connected graph with V vertices numbered from 0 to V-1, the task is to implement both Depth First Search (DFS) and Breadth First Search (BFS) traversals starting from the 0th vertex. The graph is represented using an adjacency list where adj[i] contains a list of vertices connected to vertex i. Visit nodes in the order they appear in the adjacency list.
Examples
Example 1:
Input: V = 5
adj = [
[2, 3, 1],
[0],
[0, 4],
[0],
[2]
]
-----
| 0 |------+
----- \
/ \ \
/ \ \
----- ----- -----
| 2 | | 3 | | 1 |
----- ----- -----
/
/
/
-----
| 4 |
-----
Output:
Explanation:
DFS = Start from vertex 0. Visit vertex 2, then vertex 4,
backtrack to vertex 0, and finally vertex 1.
The traversal is 0->2->4->3->1.
BFS = Start from vertex 0. Visit vertices 2, 3 and 1 (in the
order they appear in the adjacency list). Then, visit
vertex 4 from vertex 2.
The traversal is 0->2->3->1->4.Different Approaches
1️⃣ BFS (Breadth First Search)
Intuition:
The traversal techniques form the basics of any graph problem. One of the two traversal techniques is Breadth First Search(BFS), also known as Level Order Traversal. Breadth-First Search (BFS) is a traversal technique that explores all the neighbors of a node before moving to the next level of neighbors. It uses a queue data structure.
Approach:
- Mark all nodes as unvisited. Create an empty queue.
- Enqueue the source node. Mark the source node as visited.
- While the queue is not empty:
- Dequeue the front node. Process the node.
- For each adjacent unvisited node, enqueue the adjacent node and mark it as visited.
- Repeat the process until all nodes are visited.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Helper function to perform BFS
traversal from the node */
void bfs(int node, vector<int> adj[], int vis[],
vector<int> &ans) {
// Queue data structure
queue<int> q;
// Push the starting node
q.push(node);
// Until the queue is empty
while(!q.empty()) {
// Get the node
int node = q.front();
q.pop();
// Add the node to answer
ans.push_back(node);
// Traverse for all its neighbours
for(auto it : adj[node]) {
/* If the neighbour has previously not been
visited, store in Q and mark as visited */
if(!vis[it]) {
vis[it] = 1;
q.push(it);
}
}
}
// Return
return;
}
public:
/* Function to return a list containing
the BFS traversal of the graph */
vector<int> bfsOfGraph(int V, vector<int> adj[]) {
// Visited array
int vis[V] = {0};
// To store the result
vector<int> ans;
// Traverse all the nodes
for(int i=0; i < V; i++) {
// If the node is unvisited
if(vis[i] == 0) {
// Mark the node as visited
vis[i] = 1;
// Call BFS from that node
bfs(i, adj, vis, ans);
}
}
return ans;
}
};
int main() {
int V = 5;
vector<int> adj[] = {
{2, 3, 1},
{0},
{0, 4},
{0},
{2}
};
// Creating instance of Solution class
Solution sol;
// Function call to get the BFS traversal of graph
vector<int> bfs = sol.bfsOfGraph(V, adj);
// Output
cout << "The BFS traversal of the given graph is: ";
for(int i=0; i < bfs.size(); i++) {
cout << bfs[i] << " ";
}
cout << "\nThe DFS traversal of the given graph is: ";
for(int i=0; i < dfs.size(); i++) {
cout << dfs[i] << " ";
}
return 0;
}2️⃣ DFS (Depth First Search)
Intuition:
The traversal techniques form the basics of any graph problem. One of the two traversal techniques is Depth First Search(DFS). Depth-First Search (DFS) is a traversal technique that explores as far as possible along each branch before backtracking. It uses a stack data structure, either explicitly or implicitly through recursion.
Approach:
- Mark all nodes as unvisited. Create an empty stack or use recursion.
- Push the source node onto the stack (or call the recursive function with the source node). Mark the source node as visited.
- While the stack is not empty:
- Pop the top node from the stack. For each adjacent unvisited node, push the adjacent node onto the stack (or call the recursive function with the adjacent node).
- Mark the adjacent node as visited.
- Repeat the process until all nodes are visited.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Helper function to perform BFS
traversal from the node */
void bfs(int node, vector<int> adj[], int vis[],
vector<int> &ans) {
// Queue data structure
queue<int> q;
// Push the starting node
q.push(node);
// Until the queue is empty
while(!q.empty()) {
// Get the node
int node = q.front();
q.pop();
// Add the node to answer
ans.push_back(node);
// Traverse for all its neighbours
for(auto it : adj[node]) {
/* If the neighbour has previously not been
visited, store in Q and mark as visited */
if(!vis[it]) {
vis[it] = 1;
q.push(it);
}
}
}
// Return
return;
}
/* Helper function to recursively
perform DFS from the node */
void dfs(int node, vector<int> adj[], int vis[],
vector<int> &ans) {
// Mark the node as visited
vis[node] = 1;
// Add the node to the result
ans.push_back(node);
// Traverse all its neighbours
for(auto it : adj[node]) {
// If the neighbour is not visited
if(!vis[it]) {
// Perform DFS recursively
dfs(it, adj, vis, ans);
}
}
}
public:
/* Function to return a list containing
the DFS traversal of the graph */
vector<int> dfsOfGraph(int V, vector<int> adj[]) {
// Visited array
int vis[V] = {0};
// Create a list to store DFS
vector<int> ans;
// Traverse all the nodes
for(int i=0; i < V; i++) {
// If the node is unvisited
if(vis[i] == 0) {
// Call DFS from that node
dfs(i, adj, vis, ans);
}
}
// Return the result
return ans;
}
/* Function to return a list containing
the BFS traversal of the graph */
vector<int> bfsOfGraph(int V, vector<int> adj[]) {
// Visited array
int vis[V] = {0};
// To store the result
vector<int> ans;
// Traverse all the nodes
for(int i=0; i < V; i++) {
// If the node is unvisited
if(vis[i] == 0) {
// Mark the node as visited
vis[i] = 1;
// Call BFS from that node
bfs(i, adj, vis, ans);
}
}
return ans;
}
};
int main() {
int V = 5;
vector<int> adj[] = {
{2, 3, 1},
{0},
{0, 4},
{0},
{2}
};
// Creating instance of Solution class
Solution sol;
// Function call to get the BFS traversal of graph
vector<int> bfs = sol.bfsOfGraph(V, adj);
// Function call to get the BFS traversal of graph
vector<int> dfs = sol.dfsOfGraph(V, adj);
// Output
cout << "The BFS traversal of the given graph is: ";
for(int i=0; i < bfs.size(); i++) {
cout << bfs[i] << " ";
}
cout << "\nThe DFS traversal of the given graph is: ";
for(int i=0; i < dfs.size(); i++) {
cout << dfs[i] << " ";
}
return 0;
}