Implémentation du parcours en largeur (BFS) sur un graphe

Introduction

Dans ce laboratoire, vous allez apprendre à implémenter l'algorithme de parcours en largeur (BFS) pour un graphe en utilisant le C++. L'algorithme BFS commence par un nœud dans un graphe et explore tous les nœuds au niveau de profondeur actuel avant de passer aux nœuds au niveau suivant. Le parcours en largeur utilise la structure de données appelée File. Nous allons également expliquer en détail la structure de données File.

Configuration du projet

Accédez au répertoire project :

cd project

Créez un nouveau fichier C++ nommé main.cpp en utilisant :

touch main.cpp

Inclusion des bibliothèques nécessaires

En C++, nous utilisons iostream pour les entrées et sorties, vector pour stocker dynamiquement des éléments, et queue pour implémenter l'algorithme de parcours en largeur (BFS). Nous utilisons également le fichier d'en-tête bits/stdc++.h pour inclure toutes les bibliothèques standards. Dans le fichier main.cpp, tapez le code suivant :

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

using namespace std;

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

Implémentation de l'algorithme de parcours en largeur (BFS)

Nous allons créer une fonction nommée bfsTraversal, qui prend un nœud de départ en argument. Cette fonction va traiter l'algorithme de parcours en largeur (BFS).

void bfsTraversal(int b)
{
    queue<int> q; // Déclare une file pour stocker tous les nœuds connectés à b
    q.push(b); // Insère b dans la file
    v[b] = true; // Marque b comme visité

    cout << "\n\nLe parcours en largeur est :  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); // Supprime le premier élément de la file

        // Boucle sur tous les nœuds connectés au nœud actuel
        for (auto j = g[a].begin(); j!= g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // Ajoute le nœud connecté à la file pour traitement
            }
        }
        cout << a << "  ";
    }
}

Ajout d'arêtes au graphe

Nous allons créer une fonction nommée makeEdge qui prend deux sommets et crée une arête entre eux. Elle sera appelée pour chaque arête du graphe.

void makeEdge(int a, int b)
{
    g[a].push_back(b); // Une arête du sommet a au sommet b
}

Acceptation des informations sur le graphe

Dans cette étape, nous allons accepter les informations sur le graphe à partir de l'utilisateur, y compris le nombre de sommets et d'arêtes, les sommets source et cible des arêtes, et initialiser les vecteurs.

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

    cout << "Entrez le nombre de sommets : ";
    cin >> n;

    cout << "Entrez le nombre d'arêtes : ";
    cin >> e;

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

    cout << "Entrez les arêtes avec le sommet source et le sommet cible : ";

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

Compilation et exécution du programme

L'étape suivante est de compiler et d'exécuter le code. Dans le terminal, exécutez la commande suivante :

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

Vous devriez être capable de voir la sortie de l'algorithme de parcours en largeur (BFS) du graphe sur le terminal.

Code complet du fichier 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\nLe parcours en largeur est :  ";

    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 << "Entrez le nombre de sommets : ";
    cin >> n;

    cout << "Entrez le nombre d'arêtes : ";
    cin >> e;

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

    cout << "Entrez les arêtes avec le sommet source et le sommet cible : ";

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

Sommaire

Dans ce laboratoire, vous avez appris à implémenter l'algorithme de parcours en largeur (BFS) sur un graphe en utilisant le C++. L'algorithme commence par un nœud de départ et explore tous les nœuds du graphe. Nous avons utilisé une structure de données de file pour implémenter l'algorithme BFS. En complétant ce laboratoire, vous avez acquis une meilleure compréhension des algorithmes de parcours de graphe.