C++ 深度优先搜索
时间: 2023-11-08 15:05:43 浏览: 57
深度优先搜索(Depth First Search,DFS)是一种用于遍历或搜索树或图的算法。它从根节点开始,沿着路径直到达到叶子节点,然后回溯到前一个节点,继续搜索未探索的分支。DFS 使用栈来保存路径上的节点。
下面是深度优先搜索的伪代码:
1. 创建一个空栈,将起始节点压入栈中
2. 创建一个空集合,用于记录已访问的节点
3. 当栈不为空时,执行以下步骤:
- 从栈中弹出一个节点
- 如果弹出的节点是目标节点,则搜索成功,结束
- 如果弹出的节点没有被访问过,则将其标记为已访问,并将其未访问的邻居节点压入栈中
4. 如果栈为空且未找到目标节点,则搜索失败
深度优先搜索的时间复杂度为 O(V + E),其中 V 是节点数,E 是边数。如果搜索完整个图或树,那么每个节点都会被访问一次。
相关问题
C++深度优先搜索全排列
以下是C++实现深度优先搜索全排列的代码示例:
```cpp
#include <iostream>
#include <vector>
using namespace std;
void dfs(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& res) {
if (path.size() == nums.size()) { // 如果路径长度等于数组长度,说明已经找到一组解
res.push_back(path); // 将路径加入结果集
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!used[i]) { // 如果当前数字没有被使用过
used[i] = true; // 标记为已使用
path.push_back(nums[i]); // 将当前数字加入路径
dfs(nums, path, used, res); // 继续搜索下一个数字
path.pop_back(); // 回溯,将当前数字从路径中删除
used[i] = false; // 标记为未使用
}
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res; // 存储结果集
vector<int> path; // 存储路径
vector<bool> used(nums.size(), false); // 标记数字是否被使用过
dfs(nums, path, used, res); // 开始搜索
return res;
}
int main() {
vector<int> nums = {1, 2, 3};
vector<vector<int>> res = permute(nums);
for (auto& path : res) {
for (auto& num : path) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
```
C++深度优先搜索代码
以下是一个简单的 C 语言深度优先搜索(DFS)代码示例:
```c
#include <stdio.h>
#define MAX_N 100
int n; // 图中节点的数量
int g[MAX_N][MAX_N]; // 图的邻接矩阵
int visited[MAX_N]; // 标记节点是否已经被访问
void dfs(int u) {
visited[u] = 1; // 标记节点 u 已经被访问
printf("%d ", u); // 输出节点 u 的编号
for (int v = 0; v < n; v++) {
if (g[u][v] && !visited[v]) { // 如果节点 u 和节点 v 之间有边,并且节点 v 没有被访问过
dfs(v); // 递归访问节点 v
}
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &g[i][j]);
}
}
dfs(0); // 从节点 0 开始深度优先搜索
return 0;
}
```
这段代码实现了一个简单的深度优先搜索算法,用于遍历一个给定的图。在这个算法中,我们首先标记起点节点已经被访问过,然后递归访问与其相邻的未被访问过的节点,直到所有节点都被访问过为止。