遍历算法
BFS（广度优先遍历）
1. 什么是 BFS？
BFS（广度优先搜索）是一种图的遍历算法，用于从一个起始节点出发，逐层访问图中的所有节点。其基本流程如下：
- 起始节点：选择一个节点作为起点。
- 队列：使用队列（FIFO）来保存待访问的节点。
- 访问过程：
- 将起始节点加入队列并标记为已访问。
- 当队列不为空时：
- 从队列中取出一个节点，访问该节点。
- 将该节点的所有未访问邻居节点加入队列并标记为已访问。
- 层级遍历：BFS 会先访问距离起始节点最近的节点，然后逐层向外扩展，直到所有可以访问的节点都被访问。
2. 特点和应用
- 最短路径：在无权图中，BFS 可以找到从起始节点到其他节点的最短路径。
- 图的连通性：可以用来判断图的连通性，即判断两个节点是否在同一连通分量中。
- 应用：广泛应用于网络流、社交网络分析、最短路径问题、迷宫求解等领域。
3. BFS 示例
假设我们有一个无向图，节点间的连接如下：
应该如何实现这种算法呢？首先我们应该用一个队列来维护节点，进入 BFS 这个接口的时候，我们应该传入从哪个节点开始进行 BFS。然后用一个队列来维护节点，先将第一个节点 push 进队列中，然后将这个节点输出之后，先将这个节点保存起来然后再把这个节点 pop 掉，然后将与这个节点相连的节点 push 进队列（注意：这里可能会出现重复的节点，比如我们拿上面的例子为例，第一次 push 的时候我们将 C 节点已经 push 进队列了，但是第二层访问完了之后，到第三层的时候，B 和 C 相连还会遍历一次 C，所以这里我们应该用一个 vector 进行标记，标记这个节点被访问过没有），进入循环的条件是队列是否为空。
代码展示：
void BFS(const V& src) {
size_t srci = GetVertexIndex(src);
queue<int> q;
q.push(srci); // 队列
vector<bool> visited(_vertexs.size(), );
visited[srci] = ;
levelsize = ;
n = _vertexs.();
(!q.()) {
( i = ; i < levelsize; i++) {
front = q.();
cout << front << << _vertexs[front] << ;
q.();
( i = ; i < _vertexs.(); i++) {
(_matrix[front][i] != MAX_W && visited[i] == ) {
q.(i);
visited[i] = ;
}
}
}
cout << endl;
levelsize = q.();
}
}
