What is C++ Program for BFS Traversal?

In this article, we will learn C++ Program for BFS Traversal,This free C++ tutorial for complete beginners will help you learn C++ from scratch.

C++ Program for BFS Traversal - ❤️C++ Tutorials In 2024

In C++, breadth First Search (BFS) is a method used to navigate through tree or graph data structures. It begins at the starting point or any chosen node, within the structure. Examines the neighboring nodes at the current level before progressing to nodes, at deeper levels.. In this article, we will learn the BFS traversal in C++, the implementation of the BFS traversal algorithm, and applications of the BFS algorithm.

The Breadth First Traversal (BFS) is an algorithm used for graph traversal that explores all the vertices breadthwise which means starting from a given vertex it first visits all the vertices that are on the same level and then moves to the next level. It uses the queue data structure the queue to manage the order in which nodes are visited.

Here, we will discuss the BFS Traversal for a graph which is almost similar to the BFS traversal of a tree but the difference is tree doesn’t contain cycles whereas a graph can have cycles so while traversing we may come to the same node again. To handle such a situation we categorize each vertex into two categories:

Visited
Not Visited

We will use a boolean visited array to mark all the visited vertices that lead to breath-first exploration.

Algorithm for BFS Traversal

Select a starting vertex
Create a queue and enqueue the starting vertex.
First, mark the selected start vertex as visited and add it to the visited array.
While the queue is not empty perform the following operations:
Dequeue a vertex, print it.
Take the dequeued node and for each unvisited neighbor of that node
Insert all its unvisited adjacent vertices in the queue and mark them as visited.
Repeat the above step 4 until the queue is empty.

The below example demonstrates the working of the breadth-first traversal step-by-step:

The below program demonstrates the breadth-first traversal on a graph in C++.

C++

// C++ program for Breadth-first-traversal

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// Define a class named Graph to represent the graph
// structure.
class Graph {
    // Number of vertices in the graph.
    int V;
    // Adjacency list representation of the graph.
    vector<vector<int> > adjList;

public:
    // Constructor for initializing the graph with a given
    // number of vertex
    Graph(int vertices)
    {
        V = vertices;
        adjList.resize(vertices);
    }

    // Function for adding an edge to the graph.
    void addEdge(int src, int dest)
    {
        // Add destination vertex to source vertex's list.
        adjList[src].push_back(dest);
        // Add source vertex to destination vertex's list
        // (for undirected graph).
        adjList[dest].push_back(src);
    }

    // Function to perform Breadth-First Traversal (BFS)
    // starting from a given vertex.
    void bfs(int startVertex)
    {
        // Vector to keep track of visited vertices.
        vector<bool> visited(V, false);
        // Queue to help with the BFS traversal.
        queue<int> q;
        // Mark the start vertex as visited.
        visited[startVertex] = true;
        // Enqueue the start vertex.
        q.push(startVertex);

        while (!q.empty()) {
            // point currentVertex at front vertex from the queue.
            int currentVertex = q.front();
            // Print the current vertex.
            cout << currentVertex << " ";
            // Remove the front vertex from the queue.
            q.pop();

            // Iterate through all the neighbors of the
            // current vertex.
            for (int neighbor : adjList[currentVertex]) {
                // If the neighbor vertex has not been
                // visited yet.
                if (!visited[neighbor]) {
                    // Mark the neighbor vertex as visited.
                    visited[neighbor] = true;
                    // Enqueue the neighbor vertex.
                    q.push(neighbor);
                }
            }
        }
    }
};

int main()
{
    // Create a graph with 7 vertices.
    Graph g(7);

    // Add edges to the graph.
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);

    // Perform BFS starting from vertex 2.
    cout << "Breadth-First Traversal (starting from vertex "
            "2): "
         << endl;
    g.bfs(2);

    return 0;
}

Output

Breadth-First Traversal (starting from vertex 2): 
2 0 5 6 1 3 4

Time Complexity: O(V + E), here V is the number of vertices and E is the number of edges.
Auxiliary Space: O(V)

The following are the applications of the Breadth First Traversal algorithm in C++:

It is used to find the shortest path among many paths in an unweighted graph.
It can find a minimum spanning tree for weighted graphs (if the weight is non-negative and same for each of the vertices).
It is used in peer-to-peer networks like BitTorrent to find all neighbor nodes.
It can be used to detect cycles in undirected graphs, and can also detect cycles in directed graphs.
It is used in broadcasting networks to reach all nodes.

The below table illustrates the key differences between BFS and DFS traversals of a graph.

Feature	BFS Traversal	DFS Traversal
Full Form	The BFS stands for Breadth First Search traversal.	The DFS stands for Depth First Search traversal.
Traversal Method	It explores all neighbors at the present depth	It explores as far as possible along a branch.
Data Structure Used	Queue	Stack (or recursion)
Level -wise Traversal	Yes	No
Pathfinding	It finds the shortest path in unweighted graphs	It does not guarantee the shortest path
Memory Usage	Higher, as it needs to store all children at the current level	Lower, as it only stores nodes along the current path
Traversal Order	Horizontal (level by level)	Vertical (depth by depth)
Backtracking	No	Yes

What is BFS Traversal?

The BFS traversal is a traversal algorithm that explores all the vertices in a graph at the current depth before moving on to the vertices at the next depth level.

Can a Graph Have More Than One BFS Traversal?

Yes, a graph can have more than one BFS traversal.

Which Data Structure is Used in BFS Traversal of Graph?

The data structure used in the BFS traversal of graph is Queue.

Can BFS be Used to Search in Unweighted and Weighted Graphs?

Yes, BFS can be used in both unweighted and weighted graphs.

What is the Relation Between BFS for Graph and BFS for Tree?

BFS for a graph is similar to BFS for a tree. The only difference is that, unlike trees, graphs may contain cycles.

C++ Program for BFS Traversal

What is Breadth First Traversal?

Implementing BFS Traversal in C++

Algorithm for BFS Traversal

Example to Demonstrate the Working of the BFS Algorithm