# A Quick Guide to Breadth-First Search

## 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 using namespace std;// template to work for // node of any typetemplate// Create a classclass Graph{    // To maintain edges unordered_map> 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 visited; // Create a queue queue 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 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