DFS算法测试案例介绍
时间: 2023-06-23 20:46:36 浏览: 68
DFS算法(深度优先搜索)是一种遍历或搜索树或图数据结构的算法。它从根节点或起始节点开始,沿着路径走到不能走为止,然后回溯到上一个节点,继续沿着其他路径搜索,直到所有节点都被访问为止。
下面介绍两个DFS算法的测试案例:
1. 迷宫问题
在这个问题中,我们需要在一个迷宫中寻找一条从起点到终点的路径。迷宫由一个二维数组表示,其中0表示可以通行的空格,1表示墙壁。我们可以使用DFS算法在迷宫中进行搜索。
示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int maze[5][5] = {
{0, 1, 1, 0, 1},
{0, 0, 0, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 0, 0, 0},
{1, 1, 1, 1, 0}
};
bool vis[5][5]; // 记录节点是否已经被访问
bool dfs(int x, int y) {
if (x == 4 && y == 4) {
return true; // 已经到达终点
}
vis[x][y] = true; // 标记当前节点已经被访问
if (x > 0 && maze[x-1][y] == 0 && !vis[x-1][y] && dfs(x-1, y)) {
return true; // 向上走
}
if (x < 4 && maze[x+1][y] == 0 && !vis[x+1][y] && dfs(x+1, y)) {
return true; // 向下走
}
if (y > 0 && maze[x][y-1] == 0 && !vis[x][y-1] && dfs(x, y-1)) {
return true; // 向左走
}
if (y < 4 && maze[x][y+1] == 0 && !vis[x][y+1] && dfs(x, y+1)) {
return true; // 向右走
}
return false; // 无路可走
}
int main() {
memset(vis, false, sizeof(vis)); // 初始化节点为未访问
if (dfs(0, 0)) {
cout << "找到一条路径!" << endl;
} else {
cout << "没有找到路径!" << endl;
}
return 0;
}
```
在以上代码中,我们使用一个二维数组`maze`表示迷宫,使用一个布尔数组`vis`记录节点是否已经被访问。`dfs`函数接受两个参数`x`和`y`,表示当前搜索的节点的坐标。在搜索过程中,我们首先将该节点标记为已访问,然后沿着四个方向分别搜索。如果找到一条路径,则返回`true`,否则返回`false`。
2. 判断连通图
在这个问题中,我们需要判断一个无向图是否连通。我们可以使用DFS算法在图中进行搜索,并判断所有节点是否都被访问过。
示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大节点数
bool vis[MAXN]; // 记录节点是否已经被访问
vector<int> g[MAXN]; // 图的邻接表
void dfs(int u) {
vis[u] = true; // 标记节点已经被访问
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!vis[v]) { // 如果节点未被访问,继续搜索
dfs(v);
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入节点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入边的起点和终点
g[u].push_back(v); // 添加边到邻接表
g[v].push_back(u); // 无向图需要添加反向边
}
memset(vis, false, sizeof(vis)); // 初始化节点为未访问
dfs(1); // 从任一节点开始搜索
bool connected = true;
for (int i = 1; i <= n; i++) {
if (!vis[i]) { // 如果存在未访问的节点,说明图不连通
connected = false;
break;
}
}
if (connected) {
cout << "图连通!" << endl;
} else {
cout << "图不连通!" << endl;
}
return 0;
}
```
在以上代码中,我们使用邻接表表示图,并使用一个布尔数组`vis`记录节点是否已经被访问。`dfs`函数接受一个参数`u`,表示当前搜索的节点。在搜索过程中,我们首先将该节点标记为已访问,然后继续遍历该节点的未被访问的邻居节点。最后,我们在`main`函数中从任一节点开始搜索,判断所有节点是否都被访问过,如果存在未访问的节点,则说明图不连通。