Notes on BFS and DFS

26 Aug, 2019

In this post, I will explain breadth first search and depth first search in a simple and lucid way, along with their implementation in C++.

Problem statement - Given a graph with V vertices and E edges, perform graph traversal (BFS and DFS) and print the order in which the nodes are visited.

Solution -

Breadth First Search

I will assume you already know the theory behind it and will try to explain how to code it from scratch.

We will need the following containers -

An adjacency list to store the graph, for this we can use a vector of vectors.
A boolean container which keeps track of nodes we have visited to avoid endless loop in case of cycles. For this we can use a vector of bool.
A queue data structure which adds nodes which we need to visit.

The concept is simple. We start from the source node (given by the user), add it to the queue, mark it as visited, and perform the following until the queue is empty -

Store the node in front of queue in a variable, say x, since we need to process the adjacency list of this node.
Pop the queue.
Process the adjacency list of this node (x in our case) and see if the nodes directly reachable are -
- Visited, then we move to the next node in the adjacency list of x.
- Not visited, then we mark this node as visited and push it in the queue.

That’s it. Simple enough. Now, here is the code -

 1#include <iostream>
 2#include <vector>
 3#include <queue>
 4using namespace std;
 5
 6vector<vector<int> > adjList;
 7vector<bool> visited;
 8
 9int main(){
10
11	int V; // Number of vertices
12	cout << "Enter number of vertices\n";
13	cin >> V;
14	int E; // Number of edges
15	cout << "Enter number of edges\n";
16	cin >> E;
17
18	adjList.resize(V);
19	visited.resize(V, 0);
20
21	for(int i = 0; i < E; ++i){
22		int v1, v2;
23		cin >> v1 >> v2;
24		adjList[v1].push_back(v2);
25	}
26
27	queue<int> q;
28
29	int source;
30	cout << "Enter source vertex for performing dfs\n";
31	cin >> source;
32
33	q.push(source);
34	visited[source] = 1;
35	while(!q.empty()){
36		int u = q.front();
37		cout << "Visiting node --> " << u << endl;
38		q.pop();
39		for(auto x: adjList[u]) if(!visited[x]){
40			q.push(x);
41			visited[x] = 1;
42		}
43	}
44
45	for(auto x:visited) cout << x << endl;
46}

Depth First Search

Again, hope you know the theory. I will provide a very short DFS code which doesn’t use a stack. This uses the power of recursion.

We will need the following containers -

An adjacency list to store the graph.
A boolean container to mark visited nodes.

Start the DFS from source node, mark it as visited, and for every node in its adjacency list, say x, recursively call DFS(x).

Here is the code -

 1#include <iostream>
 2#include <vector>
 3using namespace std;
 4
 5vector<vector<int> > adjList;
 6vector<bool> visited;
 7
 8void dfs(int u){
 9	cout << "Visiting node --> " << u << endl;
10	visited[u] = 1;
11	for(auto x:adjList[u]){
12		if(!visited[x]) dfs(x);
13	}
14}
15
16int main(){
17
18	int V; // Number of vertices
19	cout << "Enter number of vertices\n";
20	cin >> V;
21	int E; // Number of edges
22	cout << "Enter number of edges\n";
23	cin >> E;
24
25	adjList.resize(V);
26	visited.resize(V, 0);
27
28	for(int i = 0; i < E; ++i){
29		int v1, v2;
30		cin >> v1 >> v2;
31		adjList[v1].push_back(v2);
32	}
33
34	int source;
35	cout << "Enter source vertex for performing dfs\n";
36	cin >> source;
37
38	dfs(source);
39}

That’s it, the two most common graph search algorithms.

<< Previous Post

Next Post >>

#Algorithms