BFS Algorithm

Description

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at a selected node (typically the root or an arbitrary node in the case of a graph) and explores all of the neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

C++ Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void BFS(int start, int V, const vector<vector<int>>& adj) {
    vector<bool> visited(V, false);
    queue<int> q;

    visited[start] = true;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        cout << v << " ";
        q.pop();

        for (int i = 0; i < adj[v].size(); ++i) {
            if (!visited[adj[v][i]]) {
                visited[adj[v][i]] = true;
                q.push(adj[v][i]);
            }
        }
    }
}

int main() {
    int V = 5;
    vector<vector<int>> adj(V);

    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(0);
    adj[1].push_back(3);
    adj[1].push_back(4);
    adj[2].push_back(0);
    adj[3].push_back(1);
    adj[4].push_back(1);

    BFS(0, V, adj);

    return 0;
}

Time and Space Complexity

Operation	Time Complexity	Space Complexity
BFS Algorithm	O(V + E)	O(V)

Where:

• V: Number of vertices.
• E: Number of edges.

← Back to Homepage