Applications of Breadth First Traversal | DSA in C++ - Software Development PDF Download

Introduction

Breadth First Traversal (BFS) is a fundamental graph traversal algorithm used to explore or search through a graph in a systematic manner. It starts at a given vertex and visits all its neighbors before moving on to their neighbors, and so on. In this article, we will delve into the applications of Breadth First Traversal and provide simple code examples in C++ to help beginners understand its implementation.

What is Breadth First Traversal?

Breadth First Traversal is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order. It visits all the vertices at the same level before moving on to the next level. This algorithm uses a queue data structure to keep track of the vertices to visit.

Breadth First Traversal Algorithm

The Breadth First Traversal algorithm can be summarized in the following steps:

• Start with a source vertex.
• Enqueue the source vertex into a queue.
• Mark the source vertex as visited.
• While the queue is not empty, repeat the following steps:
  • Dequeue a vertex from the queue.
  • Process the dequeued vertex.
  • Enqueue all its unvisited neighbors into the queue and mark them as visited.

Applications of Breadth First Traversal

Shortest Path in an Unweighted Graph

Breadth First Traversal can be used to find the shortest path between two vertices in an unweighted graph. By performing a BFS from the source vertex, we can keep track of the distance from the source to each visited vertex. This information can be utilized to find the shortest path.

Finding Connected Components

Breadth First Traversal can help identify connected components in a graph. By performing a BFS from each unvisited vertex, we can find all the vertices connected to it. This process can be repeated until all vertices are visited, thus finding all the connected components in the graph.

Detecting Cycles in a Graph

BFS can also be used to detect cycles in a graph. While performing the traversal, if we encounter an already visited vertex (other than the parent of the current vertex), it indicates the presence of a cycle.

Code Examples

Breadth First Traversal Implementation

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

void BFS(vector<vector<int>>& graph, int startVertex) {

    vector<bool> visited(graph.size(), false);

    queue<int> q;

    q.push(startVertex);

    visited[startVertex] = true;

    while (!q.empty()) {

        int vertex = q.front();

        q.pop();

        cout << vertex << " ";

        for (int neighbor : graph[vertex]) {

            if (!visited[neighbor]) {

                q.push(neighbor);

                visited[neighbor] = true;

            }

        }

    }

}

int main() {

    vector<vector<int>> graph = {

        {1, 2},

        {0, 2, 3},

        {0, 1, 3},

        {1, 2}

    };

    cout << "BFS traversal starting from vertex 0: ";

    BFS(graph, 0);

    return 0;

}

Shortest Path Implementation

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

vector<int> shortestPath(vector<vector<int>>& graph, int startVertex) {

    vector<bool> visited(graph.size(), false);

    vector<int> distance(graph.size(), -1);

    queue<int> q;

    q.push(startVertex);

    visited[startVertex] = true;

    distance[startVertex] = 0;

    while (!q.empty()) {

        int vertex = q.front();

        q.pop();

        for (int neighbor : graph[vertex]) {

            if (!visited[neighbor]) {

                q.push(neighbor);

                visited[neighbor] = true;

                distance[neighbor] = distance[vertex] + 1;

            }

        }

    }

    return distance;

}

int main() {

    vector<vector<int>> graph = {

        {1, 2},

        {0, 2, 3},

        {0, 1, 3},

        {1, 2}

    };

    int startVertex = 0;

    vector<int> distances = shortestPath(graph, startVertex);

    cout << "Shortest path distances from vertex " << startVertex << ":" << endl;

    for (int i = 0; i < distances.size(); i++) {

        cout << "Vertex " << i << ": " << distances[i] << endl;

    }

    return 0;

}

Output:

Shortest path distances from vertex 0:

Vertex 0: 0

Vertex 1: 1

Vertex 2: 1

Vertex 3: 2

Sample Problems and Solutions

Problem 1: Given an undirected graph, find the number of connected components.

Perform a Breadth First Traversal from each unvisited vertex, incrementing a counter for each traversal. The final count will represent the number of connected components.

Problem 2: Find the shortest path between two vertices in an unweighted graph.

Use Breadth First Traversal to find the shortest path between the two vertices. Track the distance from the source vertex to each visited vertex and return the path accordingly.

Conclusion