如何使用c++ stack类实现深度优先搜索 - 问答

在C++中，使用stack类实现深度优先搜索（DFS）主要涉及到两个方面：递归和栈的使用。这里我们假设你已经熟悉了深度优先搜索的基本概念和递归的实现方式。下面是一个使用C++ stack类实现深度优先搜索的示例代码：

首先，你需要包含必要的头文件：

#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>

然后，定义一个图的数据结构，这里我们使用邻接表表示图：

using namespace std;

vector<unordered_map<int, int>> graph; // 邻接表表示的图

接下来，定义一个递归函数来实现深度优先搜索：

void dfs(int node, unordered_map<int, bool>& visited) {
    visited[node] = true; // 标记节点为已访问
    cout << node << " "; // 输出当前节点

    for (auto& neighbor : graph[node]) { // 遍历当前节点的所有邻居
        int nextNode = neighbor.first;
        if (!visited[nextNode]) { // 如果邻居节点未访问
            dfs(nextNode, visited); // 递归访问邻居节点
        }
    }
}

最后，在主函数中初始化图并调用dfs函数进行深度优先搜索：

int main() {
    // 初始化图，这里只是一个示例，你需要根据你的实际情况来构建图
    graph = {
        {{1, 2}, {3}}, // 节点0的邻居是1和2
        {{0}, {2}, {3}}, // 节点1的邻居是0、2和3
        {{0}, {1}, {3}}, // 节点2的邻居是0、1和3
        {{1}, {2}}, // 节点3的邻居是1和2
    };

    unordered_map<int, bool> visited; // 记录节点是否已访问
    for (int i = 0; i < graph.size(); ++i) {
        if (!visited[i]) { // 如果节点i未访问
            dfs(i, visited); // 递归访问节点i及其所有未访问的邻居节点
        }
    }

    return 0;
}

注意：在这个示例中，我们使用了邻接表表示的图，并使用unordered_map来记录节点是否已访问。你可以根据你的实际情况来调整数据结构和实现方式。另外，这个示例中的DFS实现是基于递归的，你也可以使用非递归的方式来实现DFS，例如使用stack类来模拟递归调用栈。

0 赞

0 踩