BFS

Visits all neighbors of a node first before moving to the next level.

Introduction

Breadth First Search (BFS) is a graph traversal algorithm that explores all neighbors of a node level by level before moving deeper. It uses a queue to process nodes in the order they are discovered. A visited array ensures that nodes are not revisited, making the traversal efficient and suitable for graphs with cycles.

How it Works?

1

Initialize the Queue

Create a queue (q) to store the nodes to be processed.

Add the starting node to the queue.

Mark the starting node as visited.

2

Visit the Starting Node

Print the starting node to indicate it has been visited.

3

Process Nodes in the Queue

While the queue is not empty:

  • Remove the first node from the queue (call it the current node).
  • Process the current node and remove it from the queue.
4

Repeat Until Queue is Empty

Continue processing nodes and exploring neighbors until the queue is empty.

Carousel image 1
Carousel image 2
Carousel image 3
Carousel image 4
Carousel image 5
Carousel image 6
Carousel image 7
Carousel image 8

Implementation of BFS on Graph

//bfsongraph.cpp
#include <iostream>
#include <vector>
#include<queue>
using namespace std;
void bfs(vector<vector<int>>&adjlist,vector<bool>&visited,int u){
queue<int> q;
q.push(u);
visited[u]=1;
cout<<u<<" ";
while(!q.empty()){
    int root=q.front();
    q.pop();
    for(int &ele:adjlist[root]){
        if(!visited[ele]){
            visited[ele]=1;
            q.push(ele);
            cout<<ele<<" ";
        }
    }
}
}
int main()
{
vector<vector<int>> adjlist = {
    {1, 3, 2},
    {0},
    {0, 3},
    {0, 2, 4, 5},
    {3},
    {3}};
vector<bool> visited(adjlist.size(), 0);
bfs(adjlist,visited,0);
}

Time Complexity

The time complexity of Breadth First Search (DFS) is typically O(V + E), where:

  • V is the number of vertices (nodes) in the graph.

  • E is the number of edges in the graph.

Time Complexity: O(V+E)

Why O(V + E)?

O(V): Each vertex is visited once. The algorithm marks each vertex as visited to avoid revisiting it.

O(E): Each edge is checked once, as the algorithm explores all neighboring vertices for every visited node.

Space Complexity

Queue

  • Stores vertices to be processed. Maximum size is proportional to the number of vertices in the largest level.

  • Space: 𝑂(𝑉)

Visited Array

  • To keep track of which vertices have been visited during the traversal.

  • Space: 𝑂(𝑉)

Space Complexity: O(V)