BFS

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?

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.

Visit the Starting Node

Print the starting node to indicate it has been visited.

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.

Repeat Until Queue is Empty

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

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);
}

# bfs_on_graph.py
from collections import deque

def bfs(adjlist, visited, start):
    """
    Performs BFS traversal on a graph using adjacency list
    """
    queue = deque([start])  # Initialize queue with starting node
    visited[start] = True
    result = []
    
    print(start, end=" ")  # Print starting node
    result.append(start)
    
    while queue:
        current = queue.popleft()  # Remove first element from queue
        
        # Visit all unvisited neighbors
        for neighbor in adjlist[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)
                print(neighbor, end=" ")
                result.append(neighbor)
    
    return result

# Example usage
if __name__ == "__main__":
    # Adjacency list representation
    adjlist = [
        [1, 3, 2],    # Node 0 connected to 1, 3, 2
        [0],          # Node 1 connected to 0
        [0, 3],       # Node 2 connected to 0, 3
        [0, 2, 4, 5], # Node 3 connected to 0, 2, 4, 5
        [3],          # Node 4 connected to 3
        [3]           # Node 5 connected to 3
    ]
    
    visited = [False] * len(adjlist)
    
    print("BFS Traversal starting from node 0:")
    bfs_result = bfs(adjlist, visited, 0)
    print()
    print("Traversal order:", bfs_result)

# Output: 0 1 3 2 4 5

// bfs_on_graph.js

function bfs(adjList, visited, start) {
    /**
     * Performs BFS traversal on a graph using adjacency list
     */
    const queue = [start];  // Initialize queue with starting node
    visited[start] = true;
    const result = [];
    
    process.stdout.write(start + " ");  // Print starting node
    result.push(start);
    
    while (queue.length > 0) {
        const current = queue.shift();  // Remove first element from queue
        
        // Visit all unvisited neighbors
        for (const neighbor of adjList[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
                process.stdout.write(neighbor + " ");
                result.push(neighbor);
            }
        }
    }
    
    return result;
}

// Example usage
function main() {
    // Adjacency list representation
    const adjList = [
        [1, 3, 2],     // Node 0 connected to 1, 3, 2
        [0],           // Node 1 connected to 0
        [0, 3],        // Node 2 connected to 0, 3
        [0, 2, 4, 5],  // Node 3 connected to 0, 2, 4, 5
        [3],           // Node 4 connected to 3
        [3]            // Node 5 connected to 3
    ];
    
    const visited = new Array(adjList.length).fill(false);
    
    console.log("BFS Traversal starting from node 0:");
    const bfsResult = bfs(adjList, visited, 0);
    console.log();
    console.log("Traversal order:", bfsResult);
}

main();

// Output: 0 1 3 2 4 5

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)

BFS

On this page