Implementando el recorrido BFS en un grafo

Introducción

En este laboratorio, aprenderá a implementar el algoritmo de recorrido BFS (Breadth-First Search) para un grafo utilizando C++. El algoritmo BFS comienza con un nodo en un grafo y explora todos los nodos en el nivel de profundidad actual antes de pasar a los nodos del siguiente nivel. El recorrido BFS utiliza la estructura de datos llamada Cola. También explicaremos en detalle la estructura de datos Cola.

Configurando el proyecto

Navegue hasta el directorio project:

cd project

Cree un nuevo archivo C++ llamado main.cpp, usando:

touch main.cpp

Incluyendo las bibliotecas necesarias

En C++, usamos iostream para la entrada y salida, vector para almacenar elementos dinámicamente y queue para implementar el algoritmo de recorrido BFS (Breadth-First Search). También usamos el archivo de encabezado bits/stdc++.h para incluir todas las bibliotecas estándar. En el archivo main.cpp, escriba el siguiente código:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

Implementando el algoritmo de recorrido BFS

Crearemos una función llamada bfsTraversal, que toma un nodo de inicio como argumento. Esta función procesará el algoritmo de recorrido BFS.

void bfsTraversal(int b)
{
    queue<int> q; // Declare una cola para almacenar todos los nodos conectados a b
    q.push(b); // Inserta b en la cola
    v[b] = true; // Marca b como visitado

    cout << "\n\nEl recorrido BFS es:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); // Elimina el primer elemento de la cola

        // Itera a través de todos los nodos que están conectados al nodo actual
        for (auto j = g[a].begin(); j!= g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // Agrega el nodo conectado a la cola para su procesamiento
            }
        }
        cout << a << "  ";
    }
}

Agregando aristas al grafo

Crearemos una función llamada makeEdge que toma dos vértices y crea una arista entre ellos. Se llamará para cada arista del grafo.

void makeEdge(int a, int b)
{
    g[a].push_back(b); // Una arista desde el vértice a hasta el vértice b
}

Aceptando la información del grafo

En este paso, recibiremos la información del grafo del usuario, incluyendo la cantidad de vértices y aristas, las vértices de origen y destino de las aristas, e inicializaremos los vectores.

int main()
{
    int n, e, a, b, i;

    cout << "Ingrese la cantidad de vértices: ";
    cin >> n;

    cout << "Ingrese la cantidad de aristas: ";
    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    cout << "Ingrese las aristas con el vértice de origen y destino: ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

Compilando y ejecutando el programa

El siguiente paso es compilar y ejecutar el código. En la terminal, ejecute el siguiente comando:

g++ main.cpp -o main &&./main

Debería poder ver la salida del algoritmo de recorrido BFS (Breadth-First Search) del grafo en la terminal.

Código completo del archivo main.cpp

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<bool> v;
vector<vector<int>> g;

void bfsTraversal(int b)
{
    queue<int> q;
    q.push(b);
    v[b] = true;

    cout << "\n\nEl recorrido BFS es:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop();

        for (auto j = g[a].begin(); j!= g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j);
            }
        }
        cout << a << "  ";
    }
}

void makeEdge(int a, int b)
{
    g[a].push_back(b);
}

int main()
{
    int n, e, a, b, i;

    cout << "Ingrese la cantidad de vértices: ";
    cin >> n;

    cout << "Ingrese la cantidad de aristas: ";
    cin >> e;

    v.assign(n, false);
    g.assign(n, vector<int>());

    cout << "Ingrese las aristas con el vértice de origen y destino: ";

    for (i = 0; i < e; i++)
    {
        cin >> a >> b;
        makeEdge(a, b);
    }

    for (i = 0; i < n; i++)
    {
        if (!v[i])
        {
            bfsTraversal(i);
        }
    }

    return 0;
}

Resumen

En este laboratorio, aprendiste cómo implementar el algoritmo de recorrido BFS (Breadth-First Search) en un grafo utilizando C++. El algoritmo comienza con un nodo de inicio y explora todos los nodos del grafo. Utilizamos una estructura de datos de cola para implementar el algoritmo BFS. Al completar este laboratorio, has adquirido una mejor comprensión de los algoritmos de recorrido de grafos.