c++ 宽度优先搜索
时间: 2024-08-12 11:06:01 浏览: 30
宽度优先搜索(Breadth-First Search,简称 BFS),是一种用于遍历或搜索树形数据结构(如图)或无向图的算法。在C++中,BFS通常通过队列(Queue)来实现,它的基本思想是从起点开始,逐层探索节点。具体步骤如下:
1. 将起始节点放入队列中。
2. 当队列非空时,从队列头部取出一个节点并标记它已经访问过。
3. 对于当前节点的所有未访问邻接点,将它们添加到队列的末尾,并设置它们的前驱节点为当前节点。
4. 重复步骤2和3,直到队列为空或找到目标节点。
BFS的优点包括:
- 能够找到两点之间的最短路径(如果图中没有负权重边)
- 可能会在搜索过程中遇到第一个满足条件的目标节点
相关问题
宽度优先搜索c++
宽度优先搜索(BFS)是一种图遍历算法,它从一个固定的起点开始,依次遍历离起点越来越远的节点,直到遍历完整张图。下面是 C++ 语言实现的宽度优先搜索算法示例代码:
```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++ 代码:
```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$ 的矩阵,分别表示初始状态和目标状态,输出为最少需要多少步才能从初始状态到达目标状态,以及从初始状态到达目标状态的解路径。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)