Breadth First Search ( BFS )

Graph and tree traversal using Breadth First Search (BFS) algorithm

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 the adjacency list data structure to explore the nodes adjacent to the visited (current) node.


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
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.


Python

Python: Breadth First Search (BFS) implementation in Python 3


Java

Java : Breadth First Search (BFS) implementation in Java 8


C++ : Breadth First Search (BFS) implementation in C++11

#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 of breadth-first search. Implemented in C++14

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 - 2020, Algotree.org.
All rights reserved.