Breadth First Search | Board Infinity

Introduction

In this article, we will discuss the breadth-first search or bfs algorithm. The breadth-first search algorithm for graphs is similar to the breadth-first search algorithm for trees. The only difference is, since a graph may contain a cycle so we may encounter the same node again and again. To avoid dealing with the same node again, we can divide the set of vertices into two categories:

1. Visited

2. Not visited

For this purpose, a boolean array is maintained to mark the nodes that we have encountered yet. In breadth first search algorithm, the queue is used for the traversal.

Implementation of Breadth first search algorithm

1. The very first step is to declare a queue and push the starting vertex or root.

2. Then, we need to initialize a visited array and mark it as visited.

3. We need to keep doing the following processes until our queue gets empty:

Get the vertex stored at the front of the queue and mark it as visited.
Remove this vertex from the queue.
Explore all the direct neighbours of this vertex and insert them in the queue.

The following is the implementation code of breadth first search algorithm:

Source Code

#include <bits/stdc++.h>
using namespace std;

// template to work for
// node of any type
template<typename T>

// Create a class
class Graph
{
// To maintain edges
unordered_map<T , list<T>> edges;

public:

// add edge
void add_edge(T x , T y)
{
edges[x].push_back(y);
edges[y].push_back(x);
}

// bfs () function
// for breadth first search traversal
void bfs(T src)
{
// Create a visited array of boolean type
unordered_map<T , bool> visited;

// Create a queue
queue<T> que;

// Insert the node in queue
que.push(src);

// Mark source vertex as visited
visited[src] = true;

// Iterate till queue gets empty
while(!que.empty())
{
T node = que.front();
cout << node << ' ';
que.pop();

for(T nbr : edges[node])
{
if(!visited[nbr])
{
que.push(nbr);
visited[nbr] = true;
}
}
}
}
};

int main() {

// Create an object
Graph<int> graph;

// Add edges
graph.add_edge(1, 2);
graph.add_edge(1, 3);
graph.add_edge(2, 3);
graph.add_edge(3, 4);

cout << "The Breadth First Traversal starting from the vertex 1:"
<< " \n";

// Call bfs() method
graph.bfs(1);

return 0;
}

write your code here: Coding Playground

Output

Complexity analysis

Time complexity: O(V + E) where V signifies the number of vertices and E signifies the number of edges

Space complexity: O(V) where V signifies the number of vertices

Breadth-first search for disconnected graph

A graph unlike a tree may be disconnected. In that case, we need to tweak our code a little bit. Consider the following program in which we loop over all vertices so that we don’t miss out any component:

Source Code

#include <bits/stdc++.h>
using namespace std;

// template to work for
// node of any type
template<typename T>

// Create a class
class Graph
{
// To maintain edges
unordered_map<T , list<T>> edges;

public:

// add edge
void add_edge(T x , T y)
{
edges[x].push_back(y);
edges[y].push_back(x);
}

// bfs () function
// for breadth first search traversal
void bfs(T V)
{

// Create a visited array of boolean type
unordered_map<T , bool> visited;

for(int currentNode = 1 ; currentNode <= V ; currentNode++)
{
// If already visited then skip
// the following steps
if(visited[currentNode])
continue;

T src = currentNode;

// Create a queue
queue<T> que;

// Insert the node in queue
que.push(currentNode);

// Mark source vertex as visited
visited[currentNode] = true;

// Iterate till queue gets empty
while(!que.empty())
{
T node = que.front();
cout << node << ' ';
que.pop();

for(T nbr : edges[node])
{
if(!visited[nbr])
{
que.push(nbr);
visited[nbr] = true;
}
}
}
}

}
};

int main() {

// Create an object
Graph<int> graph;

// Add edges
// Note that the graph is
// disconnected
graph.add_edge(1, 2);
graph.add_edge(2, 3);

graph.add_edge(4, 5);
graph.add_edge(4, 6);
graph.add_edge(5, 6);

cout << "The Breadth First Traversal of the graph:"
<< " \n";

// Call bfs() method
graph.bfs(6);

return 0;
}

write your code here: Coding Playground

Output

Output Description

As you can see, all the nodes have been traversed.

Conclusion

In this article, we discussed the breadth first search algorithm in graph. We also learned about how we can traverse a disconnected graph. We believe that you must have learned something new through this article.