C++ を使ったグラフ上の BFS 探索のマスター

はじめに

この実験では、C++ を使ってグラフの幅優先探索 (BFS) アルゴリズムを実装する方法を学びます。BFS アルゴリズムは、グラフ内のあるノードから始まり、次のレベルのノードに移る前に、現在の深さレベルのすべてのノードを探索します。BFS 探索では、キューと呼ばれるデータ構造が利用されます。また、キューのデータ構造についても詳しく説明します。

プロジェクトのセットアップ

project ディレクトリに移動します。

cd project

main.cpp という名前の新しい C++ ファイルを作成します。

touch main.cpp

必要なライブラリのインクルード

C++ では、入出力に iostream を、要素を動的に格納するために vector を、BFS 探索アルゴリズムを実装するために queue を使用します。また、すべての標準ライブラリを含めるために bits/stdc++.h ヘッダーファイルも使用します。main.cpp ファイルに、次のコードを入力します。

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

using namespace std;

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

BFS 探索アルゴリズムの実装

開始ノードを引数として受け取る bfsTraversal という関数を作成します。この関数は BFS 探索アルゴリズムを処理します。

void bfsTraversal(int b)
{
    queue<int> q; // b に接続されているすべてのノードを格納するキューを宣言する
    q.push(b); // キューに b を挿入する
    v[b] = true; // b を訪問済みとしてマークする

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

グラフに辺を追加する

2 つの頂点を受け取り、それらの間に辺を作成する makeEdge という関数を作成します。この関数は、グラフの各辺に対して呼び出されます。

void makeEdge(int a, int b)
{
    g[a].push_back(b); // 頂点 a から頂点 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;
}

プログラムのコンパイルと実行

次のステップは、コードをコンパイルして実行することです。ターミナルで、次のコマンドを実行します。

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

ターミナル上にグラフの BFS 探索アルゴリズムの出力が表示されるはずです。

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

まとめ

この実験では、C++ を使ってグラフ上の BFS 探索アルゴリズムを実装する方法を学びました。このアルゴリズムは、開始ノードから始まり、グラフ内のすべてのノードを探索します。BFS アルゴリズムの実装にはキューデータ構造を使用しました。この実験を完了することで、グラフ探索アルゴリズムについてより深い理解を得ることができました。

グラフ上での BFS 探索の実装