c++ - Program that checks the connectivity of the graph produces a segmentation fault

Question

I'm currently making a program to check whether a graph is fully connected. My approach is to use a depth-first search traversal algorithm, and just ensure that every node is connected. However, I'm currently getting a segmentation fault as soon as I compile the program. I've tried everything, I haven't been able to find the issue. Here's my current code:

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> adj;
vector<bool> visited;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}

int main() {
    bool connected = false;
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(1);
    dfs(3);
    for (int i = 0; i < 3; i++) {
        if (visited[i]) {
            connected = true;
        }
        else
            connected = false;
    }
    if (connected) {
        cout << "connected" << endl;
    }
    else
        cout << "it isn't connected" << endl;
}

Any suggestions, or potential solutions would be greatly appreciated. Thank you for taking the time to read this post!

question from:https://stackoverflow.com/questions/66055273/program-that-checks-the-connectivity-of-the-graph-produces-a-segmentation-fault

Answer 1

The main issue was the fact that you forgot to set the sizes of the vectors. That was causing the segmentation fault.

But there are several other issues with your code:

1. The logic to detect connectivity is not correct. In practice, with your code, the connection of the last node only determines the connectivity of the graph. And this last node is always connected, as you start from this node for the DFS.

2. Here for (int i = 0; i < 3; i++) you use a 0-indexing. You forgot that in the rest of the code, you are using 1-indexing. The best will be to use 0-indexing everywhere. Nevertheless, in the follwing code, I keep the 1-indexing, to show how to cope with it, in particular concerning the size of the arrays.

3. You should avoid the use of magic constant like 3 in the code.

#include <iostream>
#include <vector>

//using namespace std;
std::vector<std::vector<int>> adj;
std::vector<bool> visited;

void dfs(int v){
    visited[v] = true;
    for (int u : adj[v]) {
        if (!visited[u])
            dfs(u);
    }
}

int main(){
    int n_nodes = 3;
    visited.resize(n_nodes+1);      // <-- !!!
    adj.resize(n_nodes+1);      // <-- !!!

    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(1);
    dfs(3);
    
    bool connected = true;
    for(int i = 1; i <= n_nodes; i++) { // 1-indexed
        if(!visited[i]){
            connected = false;
        }
    }
    if(connected) {
        std::cout << "connected" << std::endl;
    } else {
        std::cout << "it isn't connected" << std::endl;
    }
}