Home / graphs / breadth first traversals of graph

breadth first traversals of graph

The BFS traversal of Graphs  traverses the graph in levels. Breadth-first algorithm starts with the root node and then traverses all the adjacent nodes. Then, it selects the nearest node and explores all the other unvisited nodes. This process is repeated until all the nodes in the graph are explored.This technique uses the queue data structure to store the vertices or nodes and also to determine which vertex/node should be taken up next.

The BFS traversal uses an auxiliary boolean array say visited[] which keeps track of the visited vertices. That is if visited[i] = true then it means that the i-th vertex is already visited.

algorithm:
Let S be the root/starting node of the graph.
  • Step 1: Start with node S and enqueue it to the queue.
  • Step 2: Repeat the following steps for all the nodes in the graph.
  • Step 3: Dequeue S and process it.
  • Step 4: Enqueue all the adjacent nodes of S and process them.
  • [END OF LOOP]
  • Step 6: EXIT


 Illustrations:


Let 0 be the starting node or source node. First, we enqueue it in the visited queue and all its adjacent nodes in the queue.

Next, we take one of the adjacent nodes to process i.e. 1. We mark it as visited by removing it from the queue and put its adjacent nodes in the queue (2 and 3 already in queue). As 0 is already visited, we ignore it.

Next, we dequeue node 2 and mark it as visited. Then, its adjacent node 4 is added to the queue.

Next, we dequeue 3 from the queue and mark it as visited. Node 3 has only one adjacent node i.e. 0 which is already visited. Hence, we ignore it.

At this stage, only node 4 is present in the queue. Its adjacent node 2 is already visited, hence we ignore it. Now we mark 4 as visited.


program:  in c++:

// C++ program to implement BFS traversal
// of a Graph

#include <bits/stdc++.h>
using namespace std;

// A utility function to add an edge in an
// undirected graph.
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// Function to perform BFS traversal of the given Graph
void BFS(vector<int> adj[], int V)
{
    // Initialize a boolean array
    // to keep track of visited vertices
    bool visited[V + 1];

    // Mark all vertices not-visited initially
    for (int i = 1; i <= V; i++)
        visited[i] = false;

    // Create a Queue to perform BFS
    queue<int> q;

    // Our source vertex is vertex
    // numbered 1
    int s = 1;

    // Mark S visited and Push to queue
    visited[s] = true;
    q.push(s);

    while (!q.empty()) {
        // Pop element at front and print
        int node = q.front();
        q.pop();

        cout << node << " ";

        // Traverse the nodes adjacent to the currently
        // poped element and push those elements to the
        // queue which are not already visited
        for (int i = 0; i < adj[node].size(); i++) {
            if (visited[adj[node][i]] == false) {
                // Mark it visited
                visited[adj[node][i]] = true;

                // Push it to the Queue
                q.push(adj[node][i]);
            }
        }
    }
}

// Driver code
int main()
{
    int V = 6;
    vector<int> adj[V + 1];
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 2, 4);
    addEdge(adj, 2, 5);
    addEdge(adj, 3, 5);
    addEdge(adj, 4, 5);
    addEdge(adj, 4, 6);
    addEdge(adj, 5, 6);

    BFS(adj, V);

    return 0;
}

java:
// Java code to illustrate BFS traversal 
// in a Graph

import java.util.*;

class Graph {
    
    // A utility function to add an edge in an
    // undirected graph
    static void addEdge(ArrayList<ArrayList<Integer> > adj,
                        int u, int v)
    {
        adj.get(u).add(v);
        adj.get(v).add(u);
    }
    
    // Function to perform BFS traversal of a Graph
    static void BFS(ArrayList<ArrayList<Integer> > adj, int V)
    {
        // Initialize a boolean array
        // to keep track of visited vertices
        boolean visited[] =  new boolean[V+1];
    
        // Mark all vertices not-visited initially
        for (int i = 1; i <= V; i++)
            visited[i] = false;
        
        // Create a queue for BFS 
        LinkedList<Integer> queue = new LinkedList<Integer>(); 
    
        // The start vertex or source vertex is 1
        int s = 1;
        
        // Mark the current node as 
        // visited and enqueue it 
        visited[s]=true; 
        queue.add(s);   
        
        while (queue.size() != 0) 
        { 
            // Dequeue a vertex from queue and print it 
            s = queue.poll(); 
            System.out.print(s+" "); 
  
            // Traverse the nodes adjacent to the currently
            // poped element and push those elements to the
            // queue which are not already visited
            for (int i = 0; i < adj.get(s).size(); i++) {
                
                // Fetch adjacent node
                int newNode = adj.get(s).get(i);
                
                // Check if it is not visited
                if(visited[newNode] == false)
                {
                    // Mark it visited
                    visited[newNode] = true;
                    
                    // Add it to queue
                    queue.add(newNode);
                }
            }
        } 
    }
    
    // Driver Code
    public static void main(String[] args)
    {
        // Creating a graph with 6 vertices
        int V = 6;
        ArrayList<ArrayList<Integer> > adj 
                    = new ArrayList<ArrayList<Integer> >(V+1);
        
        for (int i = 0; i < V+1; i++)
            adj.add(new ArrayList<Integer>());

        // Adding edges one by one
        addEdge(adj, 1, 2);
        addEdge(adj, 1, 3);
        addEdge(adj, 2, 4);
        addEdge(adj, 2, 5);
        addEdge(adj, 3, 5);
        addEdge(adj, 4, 5);
        addEdge(adj, 4, 6);
        addEdge(adj, 5, 6);
        
        BFS(adj, V);
    }
}


darkmode