为什么我在 DFS 中有 StackOverflow？

Question

我正在尝试在 c++ 中实现 DFS 算法。我用它来回答问题：“两个顶点是否相连？”，但是出了点问题。

有时程序会给出正确答案，有时会因 0xC00000FD 代码而崩溃。我 google 它现在知道了，那是一个 Whosebug 错误。

代码如下：

const int N = 4;                     // The minimal example I've know is a graph with 4 vertexes.
std::vector<int> graph[N];           // Our graph
int start = 0;                       // The start vertex
int finish = N - 1;                  // The finish vertex

bool dfs(int old, int v) {           // The DFS function
    if (v == finish)
        return true;
    bool ans = false;
    for (int u : graph[v]) {
        if (u != old)
            ans |= dfs(v, u);
    }
    return ans;
}

void init_graph_ok() {               // With this graph all works fine
    graph[0] = { 1 };               
    graph[1] = { 2 };                // 0 (st) -- 1 -- 2 -- 3 (fin)
    graph[2] = { 3 };
    graph[3] = {};
}
void init_graph_bad() {              // With this graph I have Whosebug
    graph[0] = { 1, 2 };
    graph[1] = { 2, 0 };             // 0 (st) -- 1 -- 2 -- 3 (fin)
    graph[2] = { 0, 3 };             // ^--------------^
    graph[3] = {};
}

int main() {
    init_graph_bad();
//  init_graph_ok();
    std::cout << dfs(-1, 0);
}

Answer 1

这是因为您的代码不止一次访问特定节点，因此您的代码会遇到无限递归。

由于无限递归调用，栈内存被填满，最后导致栈溢出错误。

解决方法：使用visited数组，允许每个节点几乎访问一次，如下所示：

const int N = 4;                     // The minimal example I've know is a graph with 4 vertexes.
std::vector<int> graph[N];           // Our graph
int start = 0;                       // The start vertex
int finish = N - 1;                  // The finish vertex

bool visited[N+1];

bool dfs(int old, int v) {           // The DFS function

    if(visited[v]){
        return true;
    }
    visited[v] = true;
    
    if (v == finish)
        return true;
        
    bool ans = false;
    
    for (int u : graph[v]) {
        if (u != old)
            ans |= dfs(v, u);
    }
    
    return ans;
}

void init_graph_ok() {               // With this graph all works fine
    graph[0] = { 1 };               
    graph[1] = { 2 };                // 0 (st) -- 1 -- 2 -- 3 (fin)
    graph[2] = { 3 };
    graph[3] = {};
}
void init_graph_bad() {              // With this graph I have Whosebug
    graph[0] = { 1, 2 };
    graph[1] = { 2, 0 };             // 0 (st) -- 1 -- 2 -- 3 (fin)
    graph[2] = { 0, 3 };             // ^--------------^
    graph[3] = {};
    memset(visited, false, N+1);
}

int main() {
    init_graph_bad();
//  init_graph_ok();
    std::cout << dfs(-1, 0);
}

PS: 不用担心 cycles，因为这个逻辑也会处理循环。

为什么我在 DFS 中有 StackOverflow？

Why I have StackOverflow in DFS?

c++

stack-overflow

algorithm

depth-first-search