如何使用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中文網其他相關文章！