Breadth-first search (BFS) is for traversing/searching tree or graph data structures. It starts at some arbitrary node and explores all of the neighbor nodes at the present depth before moving on to the nodes at the next depth level. To avoid processing a node again, a visited list is used to mark already traversed node.
In the following graph, traversal begins from vertex 0. The adjacent vertices are (3,2). Before processing 1, both the nodes (3,2) must be visited. In the following case, traversal is 0 3 2 1
Complexity
| Class | Search algorithm |
| Data structure | Graph |
| Time Complexity | O (V + E) V = number of vertices E = number of edges |
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define N 5
class Graph {
public:
vector<int> adj_[N];
void addEdge(int u, int v) {
// In case of undirected graph, to and fro traversal is allowed
adj_[u].push_back(v);
adj_[v].push_back(u);
}
void bfs(int src) {
vector<bool> visited(N, false);
vector<int> distance(N, 0);
queue<int> q;
q.push(src);
visited[src] = true;
distance[src] = 0;
vector<int> path;
while (!q.empty()) {
int u = q.front();
q.pop();
path.push_back(u);
for (auto v : adj_[u]) {
if (!visited[v]) {
q.push(v);
visited[v] = true;
distance[v] = distance[u] + 1;
}
}
}
cout << "Breadth First Traversal: starting from vertex: " << src << endl;
for (auto d : path) cout << d << " ";
cout << endl;
cout << "Distance of nodes from : " << src << endl;
for (int i = 0; i < distance.size(); i++)
cout << "to node " << i << " -> " << distance[i] << endl;
}
};
int main() {
Graph g;
g.addEdge(0, 3);
g.addEdge(0, 2);
g.addEdge(2, 1);
g.bfs(0);
}Breadth First Traversal: starting from vertex: 0 0 3 2 1 Distance of nodes from : 0 to node 0 -> 0 to node 1 -> 2 to node 2 -> 1 to node 3 -> 1
References