How to use breadth-first search algorithm in C++

Use the breadth-first search algorithm in C

The breadth-first search algorithm (BFS) is a graph search algorithm that starts from the starting point of the graph and sequentially visits Explore each node until you find the target node or traverse the entire graph. BFS uses queues to implement it. First, the starting node is added to the queue, and then its adjacent nodes are added to the queue, and so on until the queue is empty.

The following is a sample code that uses C to implement the breadth-first search algorithm:

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

In the above code, we first define the node structure of a graph Node, which contains The ID of the node, whether it has been visited, and a list of pointers to adjacent nodes. Then, we implemented the breadth-first search algorithm BFS, using a queue to save the nodes to be visited. In each loop, we take out the first node of the queue, output its ID, traverse its adjacent nodes, and add unvisited nodes to the queue. Finally, a simple graph is created in the main function and a breadth-first search is performed starting from node A.

Through this sample code, we can understand and use the breadth-first search algorithm in C to find connected nodes in the graph, solve shortest paths and other problems, and thus apply it to various practical scenarios.

The above is the detailed content of How to use breadth-first search algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!