Cara menggunakan algoritma carian pertama luas dalam C++

Gunakan algoritma carian pertama luas dalam C++

Algoritma carian pertama lebar (BFS) ialah algoritma carian graf yang bermula dari titik permulaan graf dan melawat serta meneroka setiap nod mengikut urutan sehingga nod sasaran ditemui atau keseluruhan gambar. BFS menggunakan baris gilir untuk melaksanakannya Mula-mula, nod permulaan ditambah pada baris gilir, dan kemudian nod bersebelahannya ditambah pada baris gilir, dan seterusnya sehingga baris gilir kosong.

Berikut ialah contoh kod yang menggunakan C++ untuk melaksanakan algoritma carian pertama luas:

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

Dalam kod di atas, kami mula-mula mentakrifkan struktur nod graf Node，其中包含节点的ID、是否访问过和相邻节点的指针列表。然后，我们实现了广度优先搜索算法BFS，使用队列来保存要访问的节点。在每次循环中，我们取出队列的首个节点，将其ID输出，并遍历其相邻节点，将未被访问过的节点加入队列中。最后，在mainBuat graf ringkas dalam fungsi dan mulakan keluasan- pertama dari nod A carian.

Melalui kod sampel ini, kami boleh memahami dan menggunakan algoritma carian pertama luas dalam C++ untuk mencari nod yang disambungkan dalam graf, menyelesaikan laluan terpendek dan masalah lain, dan dengan itu menerapkannya pada pelbagai senario praktikal.

Atas ialah kandungan terperinci Cara menggunakan algoritma carian pertama luas dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!