解释一下深度优先搜索
时间: 2023-12-18 09:29:45 浏览: 76
深度优先搜索(Depth First Search,DFS)是一种常见的图遍历算法,它可以用于解决很多与图相关的问题,比如连通性问题、路径问题等等。在深度优先搜索中,我们从一个起点开始,沿着一条路径一直走到底,直到不能再走为止,然后回溯到上一个节点,继续走其他的路径,直到所有的路径都被遍历完为止。
在C++中,我们可以使用递归或者栈来实现深度优先搜索。下面是一个使用递归实现深度优先搜索的示例代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大节点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记数组,记录每个节点是否被访问过
void dfs(int u) {
vis[u] = true; // 标记节点u已经被访问过
cout << u << " "; // 输出节点u
for (int i = 0; i < G[u].size(); i++) { // 遍历节点u的所有邻居
int v = G[u][i];
if (!vis[v]) { // 如果节点v没有被访问过
dfs(v); // 递归访问节点v
}
}
}
int main() {
int n, m; // n为节点数,m为边数
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v; // u和v之间有一条边
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u); // 无向图需要反向再连一次
}
dfs(1); // 从节点1开始遍历
return 0;
}
```
在上面的代码中,我们使用邻接表来表示图,vis数组用来记录每个节点是否被访问过,dfs函数用来实现深度优先搜索。在dfs函数中,我们首先标记当前节点已经被访问过,然后输出当前节点,最后遍历当前节点的所有邻居,如果邻居节点没有被访问过,则递归访问邻居节点。