Breadth First Search or BFS for a Graph | DSA in C++ - Software Development PDF Download

Overview of BFS

Implementation of BFS in C++

Graph Representation

To implement BFS, we need to represent the graph. There are various ways to represent a graph, but one of the common approaches is using an adjacency list. In an adjacency list, each vertex of the graph is associated with a list of its adjacent vertices.

BFS Algorithm

The BFS algorithm follows these steps:

• Create a queue and initialize it with the starting vertex.
• Mark the starting vertex as visited.
• Repeat until the queue is empty:
  • Dequeue a vertex from the queue.
  • Process the dequeued vertex.
  • Enqueue all its unvisited adjacent vertices and mark them as visited.
• Finish when all vertices have been visited.

C++ Code Example

Here's an example of BFS implementation in C++:

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

void bfs(vector<vector<int>>& graph, int start) {

    int numVertices = graph.size();

    vector<bool> visited(numVertices, false);

    queue<int> queue;

    visited[start] = true;

    queue.push(start);

    while (!queue.empty()) {

        int currentVertex = queue.front();

        queue.pop();

        cout << currentVertex << " ";

        for (int neighbor : graph[currentVertex]) {

            if (!visited[neighbor]) {

                visited[neighbor] = true;

                queue.push(neighbor);

            }

        }

    }

}

int main() {

    int numVertices = 7;

    vector<vector<int>> graph(numVertices);

    // Add edges to the graph

    graph[0] = {1, 2};

    graph[1] = {0, 3, 4};

    graph[2] = {0, 5, 6};

    graph[3] = {1};

    graph[4] = {1};

    graph[5] = {2};

    graph[6] = {2};

    cout << "BFS Traversal: ";

    bfs(graph, 0);

    return 0;

}

Output:

BFS Traversal: 0 1 2 3 4 5 6

Examples and Explanations

Example 1: Undirected Graph

Consider the following undirected graph:

     0

    / \

   1   2

  / \

 3   4

Using the BFS algorithm, the traversal order starting from vertex 0 will be: 0, 1, 2, 3, 4. This is because we visit the adjacent vertices at the same level before moving to the next level.

Example 2: Directed Graph

Consider the following directed graph:

   0 --> 1 --> 2

    \       /

     --> 3 <--

Using the BFS algorithm, the traversal order starting from vertex 0 will be: 0, 1, 3, 2. Note that in a directed graph, the traversal may not visit all the vertices if there are no outgoing edges from certain vertices.

Sample Problems

Problem 1: Find the shortest path between two nodes in an undirected graph.

Given an undirected graph, you can modify the BFS algorithm to find the shortest path between two nodes. While performing BFS, keep track of the parent of each visited node. Once the destination node is reached, you can backtrack from the destination node to the source node using the parent information to determine the shortest path.

Problem 2: Check if a graph is bipartite.

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to another. To check if a graph is bipartite, you can modify the BFS algorithm by assigning alternate colors (e.g., 0 and 1) to the vertices at each level. If at any point, there is an edge connecting two vertices of the same color, the graph is not bipartite.

Conclusion

Breadth First Search (BFS) is a fundamental graph traversal algorithm that visits all the vertices of a graph in a breadth-first manner. It can be implemented efficiently using a queue data structure. In this article, we explored the implementation of BFS in C++ and discussed some examples and sample problems. BFS is widely used in various applications, including shortest path algorithms, network analysis, and web crawling.