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

WBOY
Release: 2023-09-19 16:49:47
Original
738 people have browsed it

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  #include  #include  using namespace std; // 图的节点 struct Node { int id; bool visited; vector neighbors; Node(int _id) : id(_id), visited(false) {} }; // 广度优先搜索算法 void BFS(Node* start) { // 使用队列保存要访问的节点 queue 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; }
Copy after login

In the above code, we first define the node structure of a graphNode, 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 algorithmBFS, 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 themainfunction 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!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!