Meisterhaftes BFS-Traversieren von Graphen mit C++

Einführung

In diesem Labyrinth lernen Sie, wie Sie den BFS-Traversierungsalgorithmus für einen Graphen mit C++ implementieren. Der BFS-Algorithmus beginnt mit einem Knoten in einem Graphen und durchsucht alle Knoten auf der aktuellen Tiefenebene, bevor er zu den Knoten auf der nächsten Ebene übergeht. Die BFS-Traversierung nutzt die Datenstruktur Queue. Wir werden auch die Datenstruktur Queue im Detail erklären.

Projekt einrichten

Navigieren Sie zum Verzeichnis project:

cd project

Erstellen Sie eine neue C++-Datei mit dem Namen main.cpp mit:

touch main.cpp

Notwendige Bibliotheken einbinden

In C++ verwenden wir iostream für Eingabe und Ausgabe, vector für die dynamische Speicherung von Elementen und queue für die Implementierung des BFS-Traversierungsalgorithmus. Wir verwenden auch die Header-Datei bits/stdc++.h, um alle Standardbibliotheken einzubinden. Geben Sie im Datei main.cpp folgenden Code ein:

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

using namespace std;

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

Implementierung des BFS-Traversierungsalgorithmus

Wir werden eine Funktion namens bfsTraversal erstellen, die einen Startknoten als Argument nimmt. Diese Funktion wird den BFS-Traversierungsalgorithmus verarbeiten.

void bfsTraversal(int b)
{
    queue<int> q; // Deklariere eine Warteschlange, um alle mit b verbundenen Knoten zu speichern
    q.push(b); // Füge b zur Warteschlange hinzu
    v[b] = true; // Markiere b als besucht

    cout << "\n\nDer BFS-Traversierung ist:  ";

    while (!q.empty())
    {
        int a = q.front();
        q.pop(); // Lösche das erste Element aus der Warteschlange

        // Schleife durch alle Knoten, die mit dem aktuellen Knoten verbunden sind
        for (auto j = g[a].begin(); j!= g[a].end(); j++)
        {
            if (!v[*j])
            {
                v[*j] = true;
                q.push(*j); // Füge den verbundenen Knoten zur Warteschlange hinzu, um ihn zu verarbeiten
            }
        }
        cout << a << "  ";
    }
}

Kanten zum Graphen hinzufügen

Wir werden eine Funktion namens makeEdge erstellen, die zwei Knoten nimmt und eine Kante zwischen ihnen erstellt. Sie wird für jede Kante des Graphen aufgerufen.

void makeEdge(int a, int b)
{
    g[a].push_back(b); // Eine Kante von Knoten a zu Knoten b
}

Akzeptieren der Grapheninformationen

In diesem Schritt werden wir die Grapheninformationen vom Benutzer akzeptieren, einschließlich der Anzahl der Knoten und Kanten, der Quell- und Zielknoten der Kanten und initialisieren die Vektoren.

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

    cout << "Geben Sie die Anzahl der Knoten ein: ";
    cin >> n;

    cout << "Geben Sie die Anzahl der Kanten ein: ";
    cin >> e;

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

    cout << "Geben Sie die Kanten mit Quell- und Zielknoten ein: ";

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

Kompilieren und Ausführen des Programms

Der nächste Schritt ist es, den Code zu kompilieren und auszuführen. Führen Sie im Terminal folgenden Befehl aus:

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

Auf der Konsole sollten Sie die Ausgabe des BFS-Traversierungsalgorithmus für den Graphen sehen können.

Vollständiger Code der `main.cpp`-Datei

#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\nDer BFS-Traversierung lautet:  ";

    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 << "Geben Sie die Anzahl der Knoten ein: ";
    cin >> n;

    cout << "Geben Sie die Anzahl der Kanten ein: ";
    cin >> e;

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

    cout << "Geben Sie die Kanten mit Quell- und Zielknoten ein: ";

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

Zusammenfassung

In diesem Lab haben Sie gelernt, wie man den BFS-Traversierungsalgorithmus auf einem Graphen mit C++ implementiert. Der Algorithmus beginnt mit einem Startknoten und durchsucht alle Knoten im Graphen. Wir haben eine Warteschlange-Datenstruktur für die Implementierung des BFS-Algorithmus verwendet. Durch die Fertigstellung dieses Labs haben Sie ein besseres Verständnis von Graphen-Traversierungsalgorithmen entwickelt.

Implementierung des BFS-Traversierungsalgorithmus für Graphen