C++ で幅優先検索アルゴリズムを使用する方法

C で幅優先検索アルゴリズムを使用する

幅優先検索アルゴリズム (BFS) は、グラフの開始点から開始して、ターゲット ノードが見つかるまで、またはグラフ全体を走査するまで、各ノードを順番に探索します。 BFS はキューを使用して実装します。最初に開始ノードがキューに追加され、次にその隣接ノードがキューに追加され、キューが空になるまで同様に追加されます。

以下は、C を使用して幅優先検索アルゴリズムを実装するサンプル コードです。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 图的节点
struct Node {
    int id;
    bool visited;
    vector<Node*> neighbors;
    Node(int _id) : id(_id), visited(false) {}
};

// 广度优先搜索算法
void BFS(Node* start) {
    // 使用队列保存要访问的节点
    queue<Node*> q;
    // 标记起点已经被访问
    start->visited = true;
    q.push(start);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        cout << current->id << " ";

        // 遍历当前节点的相邻节点
        for (Node* neighbor : current->neighbors) {
            // 如果相邻节点未被访问，则标记为已访问并入队
            if (!neighbor->visited) {
                neighbor->visited = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 创建图的节点
    Node* A = new Node(1);
    Node* B = new Node(2);
    Node* C = new Node(3);
    Node* D = new Node(4);
    Node* E = new Node(5);

    // 构建节点之间的连接关系
    A->neighbors.push_back(B);
    A->neighbors.push_back(C);
    B->neighbors.push_back(A);
    B->neighbors.push_back(D);
    C->neighbors.push_back(A);
    C->neighbors.push_back(D);
    D->neighbors.push_back(B);
    D->neighbors.push_back(C);
    D->neighbors.push_back(E);
    E->neighbors.push_back(D);

    // 从节点A开始进行广度优先搜索
    cout << "BFS traversal starting from node A: ";
    BFS(A);

    return 0;
}

上記のコードでは、最初にグラフのノード構造を定義します Node には、ノードの ID、訪問済みかどうか、および隣接するノードへのポインターのリストが含まれます。次に、訪問するノードを保存するキューを使用して、幅優先検索アルゴリズム BFS#​​## を実装しました。各ループでは、キューの最初のノードを取り出し、その ID を出力し、隣接するノードを走査し、未訪問のノードをキューに追加します。最後に、main 関数で単純なグラフが作成され、ノード A から開始して幅優先検索が実行されます。

このサンプル コードを通じて、C の幅優先探索アルゴリズムを理解し、使用して、グラフ内の接続されたノードを見つけ、最短経路やその他の問題を解決し、それをさまざまな実際のシナリオに適用することができます。

以上がC++ で幅優先検索アルゴリズムを使用する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。