检查图形连通性的程序产生分段错误

Question

我目前正在编写一个程序来检查图形是否完全连接。我的做法是采用深度优先搜索遍历算法，保证每个节点都连通即可。但是，我目前在编译程序时遇到分段错误。我已经尝试了一切，我无法找到问题所在。这是我当前的代码：

#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;
}

如有任何建议或可能的解决方案，我们将不胜感激。感谢您花时间阅读这篇文章 post！

Answer 1

主要问题是您忘记设置矢量的大小。那是导致分段错误的原因。

但是您的代码还有其他几个问题：

检测连通性的逻辑不正确。实际上，对于您的代码，最后一个节点的连接仅决定图形的连接性。最后一个节点始终处于连接状态，因为您从该节点开始进行 DFS。
这里 for (int i = 0; i < 3; i++) 你使用了 0 索引。您忘记了在其余代码中，您使用的是 1 索引。最好的办法是到处使用 0 索引。尽管如此，在下面的代码中，我保留了 1 索引，以显示如何处理它，特别是关于数组的大小。
你应该避免在代码中使用像3这样的魔术常量。

#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;
    }
}

检查图形连通性的程序产生分段错误

Program that checks the connectivity of the graph produces a segmentation fault

c++

graph-theory

depth-first-search