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> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记节点是否已经访问过

void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // 处理节点 u
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

int main() {
    // 构建图
    G[1].push_back(2);
    G[1].push_back(3);
    G[2].push_back(4);
    G[2].push_back(5);
    G[3].push_back(5);
    G[4].push_back(6);
    G[5].push_back(6);
    // 从节点 1 开始进行宽度优先搜索
    bfs(1);
    return 0;
}

上述代码中，我们首先定义了一个邻接表数组 `G`，用于存储图的边信息。然后定义了一个标记数组 `vis`，用于标记每个节点是否被访问过。在 `bfs` 函数中，我们使用了 `queue` 容器来实现宽度优先搜索，从起始节点 `s` 开始进行搜索。在搜索过程中，我们首先将起始节点 `s` 入队，并将其标记为已访问。接着，我们不断从队列中取出节点进行扩展，扩展过程中将未访问过的邻居节点入队，并将其标记为已访问。最终，所有与起始节点 `s` 连通的节点都会被访问一遍。

宽度优先八数码c++

下面是一个基于宽度优先搜索算法实现的八数码问题解决程序的 C++ 代码：

#include <iostream>
#include <queue>
#include <map>
#include <cstring>
using namespace std;

// 八数码的状态结构体
struct node {
    int num[3][3]; // 表示八数码的矩阵
    int x, y;      // 空格的位置
    int step;      // 到达当前状态的步数
    int pre;       // 前驱状态的编号
} s, e, u, v;

int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; // 阶乘
int dx[] = {-1, 0, 1, 0}; // 上下左右移动
int dy[] = {0, 1, 0, -1};

int cantor(int a[]) { // 康拓展开
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        int t = 0;
        for (int j = i + 1; j < 9; j++)
            if (a[i] > a[j])
                t++;
        sum += t * fac[9 - i - 1];
    }
    return sum;
}

void reverse_cantor(int x, int a[]) { // 康拓展开的逆运算
    int vis[10] = {0};
    for (int i = 0; i < 9; i++) {
        int t = x / fac[9 - i - 1];
        x %= fac[9 - i - 1];
        for (int j = 1; j <= 9; j++)
            if (!vis[j]) {
                if (t == 0) {
                    a[i] = j;
                    vis[j] = 1;
                    break;
                } else
                    t--;
            }
    }
}

int bfs() {
    queue<node> q;
    map<int, int> mp;
    s.step = 0;
    s.pre = -1;
    int a[10];
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            a[i * 3 + j] = s.num[i][j];
    mp[cantor(a)] = 1;
    q.push(s);
    while (!q.empty()) {
        u = q.front();
        q.pop();
        if (memcmp(u.num, e.num, sizeof(u.num)) == 0)
            return u.pre;
        for (int i = 0; i < 4; i++) {
            int nx = u.x + dx[i], ny = u.y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                memcpy(&v, &u, sizeof(u));
                swap(v.num[u.x][u.y], v.num[nx][ny]);
                v.x = nx, v.y = ny;
                v.step++;
                int a[10];
                for (int i = 0; i < 3; i++)
                    for (int j = 0; j < 3; j++)
                        a[i * 3 + j] = v.num[i][j];
                int code = cantor(a);
                if (!mp[code]) {
                    mp[code] = 1;
                    v.pre = mp.size() - 1;
                    q.push(v);
                }
            }
        }
    }
    return -1;
}

int main() {
    // 输入初始状态和目标状态
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++) {
            cin >> s.num[i][j];
            if (s.num[i][j] == 0)
                s.x = i, s.y = j;
        }
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> e.num[i][j];
    int ans = bfs();
    if (ans == -1)
        cout << "无解" << endl;
    else {
        cout << "步数为：" << u.step << endl;
        int path[1000], cnt = 0;
        while (ans != -1) {
            path[cnt++] = u.pre;
            u = q[u.pre];
        }
        cout << "解路径为：";
        for (int i = cnt - 1; i >= 0; i--)
            cout << " " << path[i];
        cout << endl;
    }
    return 0;
}

其中，`cantor` 函数实现康拓展开，用于将每个状态映射到一个唯一的整数上；`reverse_cantor` 函数实现康拓展开的逆运算，用于从一个整数反推出对应的状态；`bfs` 函数实现基于宽度优先搜索算法的八数码问题的解决。程序的输入为两个 $3\times3$ 的矩阵，分别表示初始状态和目标状态，输出为最少需要多少步才能从初始状态到达目标状态，以及从初始状态到达目标状态的解路径。