Implementando a Travessia BFS em um Gráfico

Introdução

Neste laboratório, você aprenderá como implementar o algoritmo de travessia BFS (Breadth-First Search) para um grafo usando C++. O algoritmo BFS começa com um nó em um grafo e explora todos os nós no nível de profundidade atual antes de passar para os nós no próximo nível. A travessia BFS utiliza a estrutura de dados chamada Fila (Queue). Explicaremos a estrutura de dados Fila em detalhes também.

Configurando o projeto

Navegue até o diretório project:

cd project

Crie um novo arquivo C++ chamado main.cpp, usando:

touch main.cpp

Incluindo as bibliotecas necessárias

Em C++, usamos iostream para entrada e saída, vector para armazenar elementos dinamicamente e queue para implementar o algoritmo de travessia BFS. Também usamos o arquivo de cabeçalho bits/stdc++.h para incluir todas as bibliotecas padrão. No arquivo main.cpp, digite o seguinte código:

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

using namespace std;

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

Implementando o Algoritmo de Travessia BFS

Criaremos uma função chamada bfsTraversal, que recebe um nó inicial como argumento. Esta função processará o algoritmo de travessia BFS.

void bfsTraversal(int b)
{
    queue<int> q; // Declare a queue to store all the nodes connected to b
    q.push(b); // Insert b to queue
    v[b] = true; // Mark b as visited

    cout << "\n\nThe BFS Traversal is:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); // Delete the first element from the queue

        // Loop through all the nodes that are connected to the current node
        for (auto j = g[a].begin(); j != g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // Add the connected node to the queue for processing
            }
        }
        cout << a << "  ";
    }
}

Adicionando Arestas ao Gráfico

Criaremos uma função chamada makeEdge que recebe dois vértices e cria uma aresta entre eles. Ela será chamada para cada aresta do gráfico.

void makeEdge(int a, int b)
{
    g[a].push_back(b); // An edge from vertex a to vertex b
}

Aceitando as Informações do Gráfico

Nesta etapa, aceitaremos as informações do gráfico do usuário, incluindo o número de vértices e arestas, os vértices de origem e destino das arestas, e inicializaremos os vetores.

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

    cout << "Enter the number of vertices: ";
    cin >> n;

    cout << "Enter the number of edges: ";
    cin >> e;

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

    cout << "Enter the edges with source and target vertex: ";

    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 e Executando o Programa

O próximo passo é compilar e executar o código. No terminal, execute o seguinte comando:

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

Você deverá ser capaz de ver a saída do algoritmo de travessia BFS (Busca em Largura) do gráfico no terminal.

Código completo do arquivo 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\nThe BFS Traversal is:  ";

    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 << "Enter the number of vertices: ";
    cin >> n;

    cout << "Enter the number of edges: ";
    cin >> e;

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

    cout << "Enter the edges with source and target vertex: ";

    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;
}

Resumo

Neste laboratório, você aprendeu como implementar o algoritmo de travessia BFS (Busca em Largura) em um gráfico usando C++. O algoritmo começa com um nó inicial e explora todos os nós no gráfico. Usamos uma estrutura de dados de fila (queue) para implementar o algoritmo BFS. Ao completar este laboratório, você desenvolveu uma melhor compreensão dos algoritmos de travessia de grafos.