So verwenden Sie den Breitensuchalgorithmus in C++

Verwendung des Breitensuchalgorithmus in C++

Der Breitensuchalgorithmus (BFS) ist ein Diagrammsuchalgorithmus, der am Startpunkt des Diagramms beginnt und jeden Knoten nacheinander besucht und durchsucht, bis der Zielknoten erreicht ist gefunden oder das gesamte Bild. BFS verwendet Warteschlangen, um es zu implementieren. Zuerst wird der Startknoten zur Warteschlange hinzugefügt, dann werden die angrenzenden Knoten zur Warteschlange hinzugefügt und so weiter, bis die Warteschlange leer ist.

Das Folgende ist ein Beispielcode, der C++ verwendet, um den Breitensuchalgorithmus zu implementieren:

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

Im obigen Code definieren wir zunächst die Knotenstruktur eines Diagramms. Node，其中包含节点的ID、是否访问过和相邻节点的指针列表。然后，我们实现了广度优先搜索算法BFS，使用队列来保存要访问的节点。在每次循环中，我们取出队列的首个节点，将其ID输出，并遍历其相邻节点，将未被访问过的节点加入队列中。最后，在mainErstellen Sie ein einfaches Diagramm in der Funktion und beginnen Sie mit der Breitensuche. Zuerst von Knoten A suchen.

Durch diesen Beispielcode können wir den Breitensuchalgorithmus in C++ verstehen und verwenden, um verbundene Knoten im Diagramm zu finden, kürzeste Pfade und andere Probleme zu lösen und ihn so auf verschiedene praktische Szenarien anzuwenden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Breitensuchalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!