在C++中实现深度优先搜索时避免堆栈溢出

Question

网格中三角形面的连通分量

\n

我已经使用上面的链接实现了深度优先搜索，并且对于我的大多数数据样本都运行良好。当我的数据样本非常大时，代码会达到断点，由于递归函数变得太深，可能会导致堆栈溢出。有什么办法可以避免这种情况吗？或者我是否必须使用其他方式（例如广度优先搜索/并集查找算法）来查找图中的连接组件。

\n

#include <bits/stdc++.h>\nusing namespace std;\n \nclass Graph {\n \n    // A function used by DFS\n    void DFSUtil(int v);\n \npublic:\n    int count;\n    map<int, bool> visited;\n    map<int, list<int> > adj;\n    // function to add an edge to graph\n    void addEdge(int v, int w);\n \n    // prints DFS traversal of the complete graph\n    void DFS();\n};\n \nvoid Graph::addEdge(int v, int w)\n{\n    adj[v].push_back(w); // Add w to v\xe2\x80\x99s list.\n}\n \nvoid Graph::DFSUtil(int v)\n{\n    // Mark the current node as visited and print it\n    visited[v] = true;\n    cout << v << " ";\n \n    // Recur for all the vertices adjacent to this vertex\n    list<int>::iterator i;\n    for (i = adj[v].begin(); i != adj[v].end(); ++i)\n        if (!visited[*i])\n            DFSUtil(*i);\n}\n \n// The function to do DFS traversal. It uses recursive\n// DFSUtil()\nvoid Graph::DFS()\n{   \n    count = 0;\n    // Call the recursive helper function to print DFS\n    // traversal starting from all vertices one by one\n    for (auto i : adj)\n        if (visited[i.first] == false)\n         {\n            DFSUtil(i.first);\n            count++;\n         }\n}\n \nint main()\n{\n    // Create a graph given in the above diagram\n    Graph g;\n    for face in faces :\n    {\n       g.addEdge(face[0], face[1]);\n       g.addEdge(face[0], face[2]);\n       g.addEdge(face[1], face[0]);\n       g.addEdge(face[1], face[2]);\n       g.addEdge(face[2], face[0]);\n       g.addEdge(face[2], face[1]);\n    }\n    \n \n    cout << "Following is Depth First Traversal \\n";\n       \n      // Function call\n    g.DFS();\n    cout << "number of connected components = " << g.count << "\\n";\n    return 0;\n}\n

\n

Answer 1

使用递归算法，无法避免堆栈溢出。但是，您需要使用堆栈通过迭代版本重新实现您的算法。

这是一个粗略的实现。

void Graph::DFSUtil(int v)
{
    stack<int> stack;
    stack.push(v);
    cout << v << " ";
    while (!stack.empty())
    {
        int v = stack.top();
        stack.pop();
        if (!visited[v])
        {
            cout << v << " ";
            visited[v] = true;
        }
        for (int i = adj[v].begin(); i != adj[v].end(); ++i)
            if (!visited[*i])
                stack.push(*i);
    }
}