为什么我在DFS中有StackOverflow

Question

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

有时程序给出正确答案，有时与0xC00000FD代码一起崩溃。我已经用谷歌搜索过了，现在知道这是一个StackOverflow错误。

这是代码：

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 StackOverflow
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 StackOverflow
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:不要担心周期，因为这个逻辑也会处理周期。