Breadth First Search ( BFS ) Algorithm

Key points

  • Breadth First Search (BFS) is an algorithm for traversing an unweighted Graph or a Tree.
  • BFS starts with the root node and explores each adjacent node before exploring node(s) at the next level.
  • BFS makes use of Queue for storing the visited nodes of the graph / tree.

Example : Consider the below step-by-step BFS traversal of the tree. If the source is root ( node 0 ), the immediately connected nodes 1 & 2 are considered at the same level and are explored before the other nodes in the tree.

BFS_Example_Run



Algorithm : Breadth first search (Graph G, Souce_Vertex S)

1.    Create a queue Q to store the vertices.
2.    Push the source vertex S in the queue Q.
3.    Mark S as visited.
4.    While the queue Q is not empty
5.        Remove vertex U from the front of the queue. i.e Vertex U = Q.front(), Q.pop()
6.        For every vertex V adjacent to the vertex U
7.            If the vertex V is not visited Then
8.               Explore the vertex V and mark V as visited.
9.               Push the vertex V in the queue Q.


Example of breadth-first search traversal on a graph : In the below unweighted graph, the BFS algorithm beings by exploring node ‘0’ and its adjacent vertices (node ‘1’ and node ‘2’) before exploring node ‘3’ which is at the next level.

BFS_Graph

Example of breadth-first search traversal on a tree : In the below tree, the BFS algorithm beings by exploring node ‘0’ and its adjacent vertices (node ‘1’, ‘2’ and ‘3’) before exploring node ‘4’ which is at the next level.
BFS_Tree


Data structure used for storing graph : Adjacency list
Data structure used for breadth first search : Queue
Time complexity of breadth first search : O ( V + E ) for an adjacency list implementation of a graph. ‘V’ is the number of vertices and ‘E’ is the number of edges in a graph.



Breadth First Search Implementation

from collections import defaultdict

class Graph:

    def __init__(self, nodes : int) :
        # Store the adjacency list as a dictionary
        # { 0 : [ 1, 2 ], 1 : [ 3, 4 ] }
        # The default dictionary would create an empty list as a default (value) 
        # for the nonexistent keys.
        self.adjlist = defaultdict(list)
        self.nodes = nodes
        self.visited = [False] * nodes

    def AddEdge (self, src : int, dst : int) :

        self.adjlist[src].append(dst)
        self.adjlist[dst].append(src)

    def BFS (self, src : int) :

        Q = []
        Q.append(src)
        self.visited[src] = True
        print(src, end = ' ')

        while Q :

            node = Q.pop(0)

            if node in self.adjlist : # Check if the key (node) exists in the dictionary (adjlist)
               for adj_node in self.adjlist[node] :
                   if self.visited[adj_node] == False :
                       Q.append(adj_node)
                       self.visited[adj_node] = True
                       print(adj_node, end = ' ')

        # Reset the visited array for next iteration of breadth first search
        self.visited = [False] * self.nodes

    def Display_AdjList (self) :
        for item in self.adjlist.items() :
            print (item)

def main():

    nodes = 7

    g = Graph(nodes)

    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 3)
    g.AddEdge(1, 4)
    g.AddEdge(2, 3)
    g.AddEdge(3, 5)
    g.AddEdge(4, 6)
    g.AddEdge(5, 6)

    print("BFS Graph Traversal")
    print("Adjacency list for storing graph")
    g.Display_AdjList()
    print("Source Node 0 :", end = " ")
    g.BFS(0)
    print("\nSource Node 3 :", end = " ")
    g.BFS(3)

    nodes = 10
    t = Graph(nodes)

    t.AddEdge(0,1)
    t.AddEdge(0,2)
    t.AddEdge(0,3)
    t.AddEdge(1,4)
    t.AddEdge(1,5)
    t.AddEdge(1,6)
    t.AddEdge(3,7)
    t.AddEdge(3,8)
    t.AddEdge(4,9)

    print("\n\nBFS Tree Traversal")
    print("Adjacency list for storing tree")
    t.Display_AdjList()
    print("Root Node (0): ", end = " ")
    t.BFS(0)
    print("\nRoot Node (9): ", end = " ")
    t.BFS(9)

if __name__ == "__main__" :
    main()

Output

BFS Graph Traversal
Adjacency list for storing graph
(0, [1, 2])
(1, [0, 3, 4])
(2, [0, 3])
(3, [1, 2, 5])
(4, [1, 6])
(5, [3, 6])
(6, [4, 5])
Source Node 0 : 0 1 2 3 4 5 6 
Source Node 3 : 3 1 2 5 0 4 6 

BFS Tree Traversal
Adjacency list for storing tree
(0, [1, 2, 3])
(1, [0, 4, 5, 6])
(2, [0])
(3, [0, 7, 8])
(4, [1, 9])
(5, [1])
(6, [1])
(7, [3])
(8, [3])
(9, [4])
Root Node (0):  0 1 2 3 4 5 6 7 8 9 
Root Node (9):  9 4 1 0 5 6 2 3 7 8
#include<iostream>
#include<list>
#include<queue>
#include<vector>

using namespace std;

class Graph {

    private:
        int vertices;
        list<int> *adjlist;
        vector<bool> visited;
    public:
        Graph () {
        }

        Graph (int nodes) { 
            adjlist = new list<int> [nodes];
            visited.resize(nodes, false);  
            vertices = nodes;
        }

        ~Graph () { 
            delete [] adjlist;
        }

        void AddEdge (int src, int dst) {
            adjlist[src].push_back(dst);
            adjlist[dst].push_back(src);
        }
    
        void BFS (int source) {

            queue<int> Q;
            visited[source] = true;
            Q.push(source);

            while (!Q.empty()) {

                int node = Q.front();
                Q.pop();
                cout << node << " ";

                for (auto& adj_node : adjlist[node]) {
                    if (!visited[adj_node]) {
                        visited[adj_node] = true;
                        Q.push(adj_node);
                    }
                }
            }
            // Reset the visited array for next iteration of breadth first search
            fill (visited.begin(), visited.end(), false);
        }
};

int main(){
        
    Graph g(7); 

    g.AddEdge(0,1); 
    g.AddEdge(0,2); 
    g.AddEdge(1,3); 
    g.AddEdge(1,4); 
    g.AddEdge(2,3);
    g.AddEdge(3,5); 
    g.AddEdge(4,6); 
    g.AddEdge(5,6); 

    cout << "BFS Graph Traversal" << endl;
    cout << "Source Node(0): "; g.BFS(0); cout << endl;
    cout << "Source Node(3): "; g.BFS(3); cout << endl;

    Graph t(10); 

    t.AddEdge(0,1); 
    t.AddEdge(0,2); 
    t.AddEdge(0,3); 
    t.AddEdge(1,4); 
    t.AddEdge(1,5); 
    t.AddEdge(1,6);
    t.AddEdge(3,7); 
    t.AddEdge(3,8); 
    t.AddEdge(4,9); 

    cout << "BFS Tree Traversal" << endl;
    cout << "Root Node (0): "; t.BFS(0); cout << endl;
    cout << "Root Node (9): "; t.BFS(9); cout << endl;

    return 0;
}

Output

BFS Graph Traversal
Source Node(0): 0 1 2 3 4 5 6
Source Node(3): 3 1 2 5 0 4 6

BFS Tree Traversal
Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (9): 9 4 1 0 5 6 2 3 7 8 
import java.util.List;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Arrays;

class BFSTraversal {

    static class Graph {

        Integer nodes;
        List<List<Integer>> adjlist;
        boolean[] visited;

        Graph (int arg_nodes) {
            nodes = arg_nodes;
            adjlist = new ArrayList<>(nodes);
            for (int i=0; i<nodes; i++)
                adjlist.add(new ArrayList<>());
            visited = new boolean[nodes];
        }

        void AddEdge (int src, int dst) {
            adjlist.get(src).add(dst);
            adjlist.get(dst).add(src);
        }

        // BFS implementation
        void BFS (int src) {

            Queue<Integer> Q = new LinkedList<>();
            Q.add(src);
            System.out.print(src + " ");
            visited[src] = true;

            while (!Q.isEmpty()) {

                src = Q.peek();
                Q.remove();

                for (int adj_node : adjlist.get(src)) {

                    if (!visited[adj_node]) {
                        Q.add(adj_node);
                        System.out.print(adj_node + " ");
                        visited[adj_node] = true;
                    }
                }
            }
            // Mark nodes unvisited for next traversal
            Arrays.fill(visited, false);
        }
    }

    public static void main (String[] args) {

        Graph g = new Graph(7);

        g.AddEdge(0,1);
        g.AddEdge(0,2);
        g.AddEdge(1,3);
        g.AddEdge(1,4);
        g.AddEdge(2,3);
        g.AddEdge(3,5);
        g.AddEdge(4,6);
        g.AddEdge(5,6);

        System.out.println("BFS Graph Traversal ");
        System.out.print("\nSource Node (0): "); g.BFS(0);
        System.out.print("\nSource Node (3): "); g.BFS(3);

        Graph t = new Graph(10);

        t.AddEdge(0,1);
        t.AddEdge(0,2);
        t.AddEdge(0,3);
        t.AddEdge(1,4);
        t.AddEdge(1,5);
        t.AddEdge(1,6);
        t.AddEdge(3,7);
        t.AddEdge(3,8);
        t.AddEdge(4,9);

        System.out.println("\n\nBFS Tree Traversal");
        System.out.print("\nRoot Node (0): "); t.BFS(0);
        System.out.print("\nRoot Node (9): "); t.BFS(9);
    }
}

Output

BFS Graph Traversal

Source Node (0): 0 1 2 3 4 5 6
Source Node (3): 3 1 2 5 0 4 6

BFS Tree Traversal

Root Node (0): 0 1 2 3 4 5 6 7 8 9
Root Node (9): 9 4 1 0 5 6 2 3 7 8 


Copyright (c) 2019-2024, Algotree.org.
All rights reserved.