用for不要用递归
时间: 2023-07-18 19:09:38 浏览: 30
好的,以下是 C++ 实现深度优先搜索的代码示例:
```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
unordered_set<int> visited; // 记录已经访问过的节点
void dfs(int start, vector<vector<int>>& graph) {
stack<int> s;
s.push(start);
while (!s.empty()) {
int node = s.top();
s.pop();
if (visited.count(node) != 0) {
continue;
}
visited.insert(node);
// 处理当前节点
for (int i = graph[node].size() - 1; i >= 0; i--) {
int neighbor = graph[node][i];
if (visited.count(neighbor) == 0) {
s.push(neighbor); // 将未访问过的邻居节点压入栈中
}
}
}
}
int main() {
vector<vector<int>> graph = {
{1, 2}, // 0 号节点的邻居节点为 1 和 2
{0, 2}, // 1 号节点的邻居节点为 0 和 2
{0, 1, 3}, // 2 号节点的邻居节点为 0、1 和 3
{2} // 3 号节点的邻居节点为 2
};
dfs(0, graph); // 从 0 号节点开始深度优先搜索
return 0;
}
```
与递归实现不同,这里使用了一个 `stack` 栈来存储待访问的节点。首先将起始节点压入栈中,然后进入循环,取出栈顶节点,检查它是否已经被访问过,如果是,则跳过;否则,将其加入到 `visited` 集合中,并遍历其所有邻居节点,将未访问过的邻居节点压入栈中。然后继续取出下一个栈顶节点,重复上述过程,直到栈为空为止。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)