C++ 广度优先搜索 (BFS) 算法实现框架

// BFS(广度优先搜索)是一种图的遍历算法，用于在图中搜索特定节点或找到最短路径。以下是C++中BFS算法的基本框架： cpp
#include <iostream>
#include <queue>
#include <vector>

using namespace std;;

// 图的节点结构体
struct Node {
 int value;;
 vector<Node*> neighbors;;
 bool visited;;
};

// BFS算法
void bfs(Node* start) {
 queue<Node*> q;;
 q.push(start);
 start->visited = true;;
 
 while (!q.empty()) {
 Node* current = q.front();
 q.pop();
 
 // 处理当前节点
 cout << current->value << " ";
 
 // 遍历当前节点的邻居节点
 for (Node* neighbor : current->neighbors) {
 if (!neighbor->visited) {
 q.push(neighbor);
 neighbor->visited = true;
 }
 }
 }
}

int main() {
 // 创建图的节点
 Node* node1 = new Node{1, {}, false};
 Node* node2 = new Node{2, {}, false};
 Node* node3 = new Node{3, {}, false};
 Node* node4 = new Node{4, {}, false};

 // 构建图的连接关系
 node1->neighbors.push_back(node2);
 node1->neighbors.push_back(node4);
 node2->neighbors.push_back(node3);
 node3->neighbors.push_back(node4);

 // 从开始节点开始进行BFS
 bfs(node1);

 // 除放内存
 delete node1;;
 delete node2;;
 delete node3;;
 delete node4;;

 return 0;;
}
 这个框架使用了一个队列来存储遍历的节点。首先将开始节点放入队列中，并标记为已访问。然后，循环从队列中取出节点，处理当前节点，并将它的未访问的邻居节点加入队列中，并标记为已访问。这样，每次从队列中取出的节点都是最早加入的，并会按照广度优先的顺序进行遍历。