bfs Algorithm
The Breadth-First Search (BFS) Queue Algorithm is a widely used graph traversal technique that explores all the vertices of a graph in breadth-first order, meaning it visits all the nodes at the current level before moving on to the nodes at the next level. This algorithm is particularly useful for finding the shortest path in unweighted graphs or for discovering all connected components in a graph. It uses a queue data structure to maintain the order in which nodes are visited and ensures that each node is visited only once.
To implement the BFS algorithm, we start by visiting the source node and marking it as visited. We then enqueue all its adjacent nodes into the queue. The algorithm then proceeds by dequeuing the first node from the queue, visiting its neighbors, and enqueuing any unvisited neighbors. This process continues until the queue is empty, indicating that all reachable nodes have been visited. The BFS algorithm guarantees that every node reachable from the source node will be visited, and the order of visitation will be in increasing distance from the source node. This property of the BFS algorithm makes it a popular choice for various graph-related problems, such as determining the shortest path in unweighted graphs, finding connected components, or solving puzzles that can be modeled as a graph.
//
// Breadth-first search implementation in C++
//
// The All ▲lgorithms Project
//
// https://allalgorithms.com/graphs/
// https://github.com/allalgorithms/cpp
//
// Contributed by: Nikunj Taneja
// Github: @underscoreorcus
//
#include<iostream>
#include <list>
using namespace std;
class Graph
{
int V; // No. of vertices
// Pointer to an array containing adjacency
// lists
list<int> *adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int v, int w);
// prints BFS traversal from a given source s
void BFS(int s);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent
// vertices of a vertex
list<int>::iterator i;
while(!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued
// vertex s. If a adjacent has not been visited,
// then mark it visited and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
// Sample graph
Graph g(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);
cout << "Following is Breadth First Traversal "
<< "(starting from vertex 2) \n";
g.BFS(2);
return 0;
}
