Comment utiliser l'algorithme de recherche en largeur en premier en C++

Utilisation de l'algorithme de recherche en largeur d'abord en C++

L'algorithme de recherche en largeur d'abord (BFS) est un algorithme de recherche de graphique qui commence à partir du point de départ du graphique et visite et explore chaque nœud en séquence jusqu'à ce que le nœud cible soit trouvé ou l'image entière. BFS utilise des files d'attente pour l'implémenter. Tout d'abord, le nœud de départ est ajouté à la file d'attente, puis ses nœuds adjacents sont ajoutés à la file d'attente, et ainsi de suite jusqu'à ce que la file d'attente soit vide.

Ce qui suit est un exemple de code qui utilise C++ pour implémenter l'algorithme de recherche en largeur d'abord :

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

Dans le code ci-dessus, nous définissons d'abord la structure des nœuds d'un graphe Node，其中包含节点的ID、是否访问过和相邻节点的指针列表。然后，我们实现了广度优先搜索算法BFS，使用队列来保存要访问的节点。在每次循环中，我们取出队列的首个节点，将其ID输出，并遍历其相邻节点，将未被访问过的节点加入队列中。最后，在mainCréons un graphe simple dans la fonction et commençons en largeur- d'abord à partir du nœud de recherche A.

Grâce à cet exemple de code, nous pouvons comprendre et utiliser l'algorithme de recherche en largeur d'abord en C++ pour trouver les nœuds connectés dans le graphique, résoudre les chemins les plus courts et d'autres problèmes, et ainsi l'appliquer à divers scénarios pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!