BFS usando STL para codificación competitiva

Una implementación simple basada en STL de BFS usando cola y vector en STL. La lista de adyacencia se representa mediante vectores de vector. 

En BFS, comenzamos con un Node.

1. Cree una cola y ponga en cola la fuente en ella. 
   1. Marcar fuente como visitada.
2. Si bien la cola no está vacía, haga lo siguiente
   1. Desencolar un vértice de la cola. Que esto sea f.
   2. Imprimir f
   3. Ponga en cola todos los no visitados adyacentes a f y márquelos como visitados.

A continuación se muestra un ejemplo de BFS que comienza en el vértice de origen 1. Tenga en cuenta que puede haber múltiples BFS posibles para un gráfico (incluso desde un vértice en particular). 
 

Para obtener más detalles de BFS, consulte esta publicación . 
El código aquí está simplificado de tal manera que podría usarse en codificación competitiva. 

Implementación:

// A Quick implementation of BFS using
// vectors and queue
#include <bits/stdc++.h>
#define pb push_back
 
using namespace std;
 
vector<bool> v;
vector<vector<int> > g;
 
void edge(int a, int b)
{
    g[a].pb(b);
 
    // for undirected graph add this line
    // g[b].pb(a);
}
 
void bfs(int u)
{
    queue<int> q;
 
    q.push(u);
    v[u] = true;
 
    while (!q.empty()) {
 
        int f = q.front();
        q.pop();
 
        cout << f << " ";
 
        // Enqueue all adjacent of f and mark them visited
        for (auto i = g[f].begin(); i != g[f].end(); i++) {
            if (!v[*i]) {
                q.push(*i);
                v[*i] = true;
            }
        }
    }
}
 
// Driver code
int main()
{
    int n, e;
    cin >> n >> e;
 
    v.assign(n, false);
    g.assign(n, vector<int>());
 
    int a, b;
    for (int i = 0; i < e; i++) {
        cin >> a >> b;
        edge(a, b);
    }
 
    for (int i = 0; i < n; i++) {
        if (!v[i])
            bfs(i);
    }
 
    return 0;
}

Input:
8 10
0 1
0 2
0 3
0 4
1 5
2 5
3 6
4 6
5 7
6 7

Output:
0 1 2 3 4 5 6 7

Este artículo es una contribución de Nikhil Mahendran . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.