Introduction
- Breadth first search is one of the basic and essential searching algorithms on graphs.
- The path found by breadth first search to any node is the shortest path to that node, i.e the path that contains the smallest number of edges in unweighted graphs.
Description
- The algorithm works by maintaining a Queue of adjacent vertices.
- First, we mark the source vertex as visited.
- Then, we explore all the adjacent of .
- If the adjacent vertex is not visited then we mark it as visited.
- The algorithm works until the queue is empty.
Example
Implementation
#include <bits/stdc++.h>
using namespace std;
const int maxN = 1000001;
vector<int> G[maxN];
bool visited[maxN];
void bfs(int u) {
queue<int> Q;
visited[u] = true;
Q.push(u);
while(!Q.empty()) {
int curr = Q.front();
Q.pop();
cout << curr << " ";
for (int neighbour: G[curr]) {
if (!visited[neighbour]) {
visited[neighbour] = true;
Q.push(neighbour);
}
}
}
}
int main() {
int vertices, edges;
cin >> vertices >> edges;
for (int i = 0; i < edges; i++) {
int a, b;
cin >> a >> b;
// Since it is an undirected graph, so we will update adjacency list of both nodes
G[a].push_back(b);
G[b].push_back(a);
}
cout << "BFS Traversal: ";
bfs(1); // We will start the traversal from 1st node since the graph is 1-based
cout << endl;
return 0;
}