1#include <iostream>
2#include <vector>
3#include <queue>
4using namespace std;
5
6// Function to perform Breadth First Search (BFS) on a graph
7void bfs(vector<vector<int>>& graph, int start) {
8  // Create a queue for BFS
9  queue<int> q;
10
11  // Mark the start vertex as visited and enqueue it
12  vector<bool> visited(graph.size(), false);
13  visited[start] = true;
14  q.push(start);
15
16  while (!q.empty()) {
17    // Dequeue a vertex from the queue and print it
18    int current = q.front();
19    q.pop();
20    cout << current << " ";
21
22    // Get all adjacent vertices of the dequeued vertex
23    // If an adjacent vertex has not been visited, mark it as visited
24    // and enqueue it
25    for (int i = 0; i < graph[current].size(); i++) {
26      int adjacent = graph[current][i];
27      if (!visited[adjacent]) {
28        visited[adjacent] = true;
29        q.push(adjacent);
30      }
31    }
32  }
33}
34
35int main() {
36  // Create a graph
37  vector<vector<int>> graph = {
38    {1, 2},
39    {0, 2, 3},
40    {0, 1, 3},
41    {1, 2},
42  };
43
44  // Perform BFS starting from vertex 0
45  cout << "BFS traversal:" << endl;
46  bfs(graph, 0);
47
48  return 0;
49}