DAA: Breadth First Search (BFS) for a Graph

Breadth First Search (Bfs) For A Graph

The algorithm in which all the graph nodes are traversed is known as the breadth-first search algorithm. In this algorithm, we select one node, and with the help of that node, we visit the other adjacent nodes. Once all the vertices are done of a particular node, it moves further to check another node and its adjacent vertices.

For example -  We start to search from vertex 2. It has 2 adjacent vertices(0 and 3), it goes to them and prints 0 and 3. 0 also has an adjacent vertex 1, so it goes to one then prints 1. Since 3 does not have any adjacent vertex, we return.

Output will be 2 0 3 1.

The data structure used is as follows:

1. STL list container: It stores what are the adjacent nodes to a particular node.
2. Queue: This queue will be needed for BFS traversal.

Note: The code in this article uses an adjacency list representation of the graph.

Time Complexity: O(V+E), where V is the number of vertices in the graph and E is the number of edges in the graph.

C++ code:

include 
 using namespace std;
 // Create a graph class for adjacency implemenatation
 class Graph {
     int V; // Number of vertices in the graph
 // This list of integers stores the adjacent vertices to a node list<int>* adj;
 public:
     Graph(int V); // Constructor to initialize the number of vertices and list initialization
 void addEdge(int v, int w);  // The BFS traversal will be printed from a node void BFS_Algo(int s);
 };
 // Definition of constructor
 Graph::Graph(int V)
 {
     this->V = V;
     adj = new list[V];
 }
 // Definition adding a new edge
 void Graph::addEdge(int v, int w)
 {
     adj[v].push_back(w); // Add value to graph
 }
 void Graph::BFS_Algo(int s)
 {
     // As none of the vertext is visited mark all false
     bool* visited = new bool[V];
     for (int i = 0; i < V; i++)
         visited[i] = false;
 list<int> queue; // The node is enterted to qeue and marked visited visited[s] = true; queue.push_back(s); // The iterator iterates in the adjacent vertices list<int>::iterator i; while (!queue.empty()) {     s = queue.front(); // print the vertex which was dequeues from the queue     cout << s << " ";     queue.pop_front();     // If the visited vertex is not marked true, mark it true.     for (i = adj[s].begin(); i != adj[s].end(); ++i) {         if (!visited[*i]) {             visited[*i] = true;             queue.push_back(*i);         }     } }
 }
 int main() // Main function to add Graph vertices and call BFS
 {
 Graph g(4); // A graph with 4 nodes g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); cout << "The BFS traversal from Node 2 is : "; g.BFS_Algo(2); return 0; }

Java Code:

 import java.io.*;
 import java.util.*;
 // Create a graph class for adjacency implemenatation
 class Graph {
 private
     int V; // Number of vertices in the graph
     // This list of integers stores the adjacent vertices to a node
 private
     LinkedList<Integer> adj[];
     //  Constructor to initialize the number of vertices and list initialization
  
     Graph(int v)
     {
         V = v;
         adj = new LinkedList[v];
         for (int i = 0; i < v; ++i)
             adj[i] = new LinkedList();
     }
  
     void addEdge(int v, int w)    // Add new edge to graph
  
     {
         // Adding a new vertex
         adj[v].add(w);
     }
  
     // prints BFS traversal from a given source s
     void BFS_Algo(int s)
     {
         // Mark all the vertices as not visited(By default
         // set as false)
         boolean visited[] = new boolean[V];
  
         // Create a queue for BFS
         LinkedList<Integer> queue = new LinkedList<Integer>();
  
         // Mark the current node as visited
         visited[s] = true; // and enqueue it in queue
         queue.add(s);
         // Iteate in queue
         while (queue.size() != 0) {
             // Take a vertex from queue and print it
  
             s = queue.poll();
             System.out.print(s + " ");
  
             // If any adjacent has not marked true mark it true
             // and add it to the queue
             Iterator<Integer> i = adj[s].listIterator(); // get current value
             while (i.hasNext()) {
                 int n = i.next();
                 if (!visited[n]) {
                     visited[n] = true;
                     queue.add(n);
                 }
             }
         }
     }
  
 public static void main(String args[]) // Main function of java to add vertices and call BFS
     {
         Graph g = new Graph(4);
  
         g.addEdge(0, 1);
         g.addEdge(0, 2);
         g.addEdge(1, 2);
         g.addEdge(2, 0);
         g.addEdge(2, 3);
         g.addEdge(3, 3);
  
         System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");
  
         g.BFS_Algo(2);
     }
 }