I'm trying to implement the Depth First Search(DFS) suing recursion to return a boolean value if a path exists between two Nodes in a graph. Below is my implementation. The edges input is in the form of a Vector array.

I tried debugging the program to detect where exactly I am going wrong, but I don't know why it gives a segmentation fault as soon as I call return validPath_helper(n, i, destination, visited, adjList); function in the validPath function after checking if the Node is visited or not.

bool validPath_helper(int n, int source, int destination, vector<bool> visited, vector<vector<int>> adjList){
    visited[source] = true;

    if(adjList[source][destination]){
        return true;
    }

    for(int i=0; i<adjList[source].size(); i  ){
        if(adjList[source][i]){
            return validPath_helper(n, i, destination, visited, adjList);
        }
    }
    return false;
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<bool> visited(n, false);
    vector<vector<int>> adjList(n);

    int u, v;
    for(int i=0; i<edges.size(); i  ){
        u = edges[i][0];
        v = edges[i][1];
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    for(int i=source; i<n; i  ){
        if(!visited[i]){
            return validPath_helper(n, i, destination, visited, adjList);
        }
    }
    return false;
}

Any Help would be appreciated!

CodePudding user response：

Seg faults usually occur due to access of un-allocated memory so that's what you should investigate first. You said that the validPath_helper is triggering the seg fault, so you should check that function.

In your case the culprit is this line :

if(adjList[source][destination]){
    return true;
}

Here you wanted to check that whether there is an edge between source node and destination node. But if you check back to how you created your adjacency list, you will see it is a vector of vectors that is for every node we have a list of nodes it has edges to.

For example the following graph:

1 - 2
0 - 1
1 - 3

The adjacency list will be :

0 -> 1
1 -> 0 2 3
2 -> 1
3 -> 1

Let's take source 2 and destination 3. Now when your validPath_helper is called it will check adjList[2][3] but as you see above length of adjList[2] is only 1 so there is no 4th element to check (3 is index so 4th element). This is the cause of your seg fault.

This also leads to an entirely different problem in your code that you want to check whether edge exists between 2 and 3 but instead you check whether there is a non-zero element at 4th position of 2's list.

You can fix this a couple of ways.

Way # 1

Instead of

if(adjList[source][destination]){
    return true;
}

try

for (int index = 0; index < adjList[source].size(); index  ) {
    if (adjList[source][index] == destination)
        return true;
}

You need to make this change in both the places of your validPath_helper function.

Way # 2

The above method increases the runtime of your program in case of big graphs, if you are concerned about runtime and know about hashlists this method is better.

#include <unordered_set> // at top

bool validPath_helper(int n, int source, int destination, vector<bool> visited, vector<unordered_set<int>> adjList){
    visited[source] = true;

    if(adjList[source].find(destination) != adjList[source].end()){
        return true;
    }

    for(int i: adjList[source]){
        if (!visited[i] && validPath_helper(n, i, destination, visited, adjList)) {
            return true;
        }
    }
    return false;
}

bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<bool> visited(n, false);
    vector<unordered_set<int>> adjList(n); 

    int u, v;
    for(int i=0; i<edges.size(); i  ){
        u = edges[i][0];
        v = edges[i][1];
        adjList[u].insert(v); 
        adjList[v].insert(u);
    }

    return validPath_helper(n, i, destination, visited, adjList);
}

There were a couple more bugs in your code :

1. Some unnecessary loops in both your functions.
2. You set visited to true but do not check it before calling DFS on new nodes.
3. You return the first DFS result and don't check other child nodes. (Due to return validPath_helper call in validPath_helper function.

Look into these issues too, refer to way # 2 above if you are stuck.