c++ 宽度优先搜索

宽度优先搜索（Breadth-First Search，简称 BFS），是一种用于遍历或搜索树形数据结构（如图）或无向图的算法。在C++中，BFS通常通过队列（Queue）来实现，它的基本思想是从起点开始，逐层探索节点。具体步骤如下：

1. 将起始节点放入队列中。
2. 当队列非空时，从队列头部取出一个节点并标记它已经访问过。
3. 对于当前节点的所有未访问邻接点，将它们添加到队列的末尾，并设置它们的前驱节点为当前节点。
4. 重复步骤2和3，直到队列为空或找到目标节点。

BFS的优点包括：
- 能够找到两点之间的最短路径（如果图中没有负权重边）
- 可能会在搜索过程中遇到第一个满足条件的目标节点

相关问题

宽度优先搜索c++

宽度优先搜索（BFS）是一种图遍历算法，可以用来解决很多问题，比如最短路径、连通性、拓扑排序等等。以下是一个简单的宽度优先搜索的 C++ 实现：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100; // 最大节点数
vector<int> adj[MAXN]; // 邻接表
bool vis[MAXN]; // 是否访问过

void bfs(int s) {
    queue<int> Q; // 存放节点的队列
    Q.push(s); // 将起点加入队列
    vis[s] = true; // 标记起点已被访问
    while (!Q.empty()) { // 只要队列不空，就一直搜索
        int x = Q.front(); // 取出队首节点
        Q.pop(); // 弹出队首节点
        for (int i = 0; i < adj[x].size(); i++) { // 枚举与 x 相邻的节点
            int y = adj[x][i];
            if (!vis[y]) { // 如果 y 没有被访问过
                Q.push(y); // 将 y 加入队列
                vis[y] = true; // 标记 y 已被访问
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数和边数
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y; // 输入一条边的两个端点
        adj[x].push_back(y); // 存储邻接表
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) { // 如果 i 没有被访问过
            bfs(i); // 从 i 开始搜索连通块
        }
    }
    return 0;
}

在这个实现中，我们使用邻接表来存储图，使用一个 bool 数组来标记每个节点是否被访问过，使用一个 queue 来存放待搜索的节点。首先，我们从起点开始搜索，将起点加入队列并标记为已访问。然后，只要队列不空，就不断取出队首节点 x 并枚举与 x 相邻的节点 y。如果 y 没有被访问过，我们就将 y 加入队列并标记为已访问。这样，我们就可以搜索出从起点能够到达的所有节点了。如果图不连通，我们需要对每个没有被访问过的节点都进行一次搜索，这样就可以找到所有连通块了。

宽度优先搜索模板代码C++语言

宽度优先搜索 (Breadth-First Search, BFS) 是图论中的遍历算法，它从给定的起点开始，按层次顺序逐层探索节点。下面是使用 C++ 编写的简单宽度优先搜索模板代码：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 图的邻接表表示
const int MAX_NODES = 100;
vector<int> adj[MAX_NODES];

// 用于标记节点是否已访问
bool visited[MAX_NODES] = {false};

void bfs(int start) {
    queue<int> q; // 使用队列存储待处理的节点
    visited[start] = true; // 标记起始节点为已访问

    q.push(start); // 将起始节点放入队列
    while (!q.empty()) {
        int curr = q.front(); // 取出队首节点
        cout << curr << " "; // 打印节点值
        q.pop();

        // 遍历当前节点的所有邻居
        for (int neighbor : adj[curr]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true; // 标记邻居为已访问
                q.push(neighbor); // 将未访问的邻居加入队列
            }
        }
    }
}

int main() {
    // 添加边并初始化邻接表
    // 这里假设我们手动添加了边
    // ...

    int startNode; // 起点节点
    cout << "Enter the starting node: ";
    cin >> startNode;

    bfs(startNode);
    return 0;
}

在这个代码中，`bfs` 函数接受起点 `start`，然后使用一个队列 `q` 存储需要处理的节点。当队列非空时，它会取出队首节点、访问该节点并将其所有未访问的相邻节点入队。