Why I have StackOverflow in DFS?

Question

I'm trying to implement a DFS algorithm in c++. I use it to answer the question: "are two vertexes connected or not?", but something went wrong.

Sometimes the program gives correct answer, sometimes crashes with 0xC00000FD code. I've google it and know now, that is a StackOverflow error.

Here's the code:

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

This is because your code is visiting a particular node more than once, because of which your code runs into an infinite recursion.

Because of the infinite recursive calls, the stack memory gets filled up completely and finally results into a stack overflow error.

Solution: Allow every node to be visited almost once by using a visited array as follows:

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: Do not worry about cycles, as this logic will take care of cycles as well.