Prim函数出现段错误问题求助，附代码及变量说明

先帮你梳理几个导致段错误（以及其他潜在问题）的关键点，这些都是排查这类图算法问题时常见的坑：

1. INF定义的语法错误 #

你写的#define INF 99999;后面多了个分号！预处理的时候，所有INF都会被替换成99999;，比如check[i]=INF;会变成check[i]=99999;;——虽然这在某些情况下能编译，但会导致逻辑混乱，比如当你用min函数比较时，可能因为语法问题触发意外行为。应该改成：

#define INF 99999

2. 全局容器的固定大小导致越界 #

你的visit数组和check vector都是全局的，固定了3000的大小，但如果输入的节点数n超过3000，访问check[n]或者visit[n]就会直接触发数组越界，这是段错误的头号嫌疑！

解决方法是把这两个变量移到solve函数内部，根据输入的n动态初始化：

// 删掉全局的visit和check，在solve里定义：
vector<bool> visit(n, false);
vector<ull> check(n, INF);

3. 变长数组(VLA)的使用不符合C++标准 #

你在solve里写的vector<ull>V[n];是C语言的变长数组特性，C++标准并不支持它。虽然GCC等编译器允许作为扩展，但当n很大时，栈上分配这么大的vector数组会导致栈溢出，直接触发段错误。

改成动态的vector容器：

vector<vector<ull>> V(n);

4. 动态二维数组未初始化 #

你用new分配了arr的内存，但每个元素都是未初始化的垃圾值。当算法访问到没有边的节点对时，会读取这些随机值，可能导致min函数计算出错误结果，甚至触发非法内存访问。

分配后要初始化所有元素为INF：

ull** arr = new ull*[n];
for (i = 0; i < n; i++) {
    arr[i] = new ull[n];
    // 初始化每个元素为INF
    fill(arr[i], arr[i] + n, INF);
}

5. min_element的范围错误 #

原来的min_element(check.begin(), check.end())会遍历整个3000大小的check，但实际有效节点只有前n个。当n<3000时，后面的元素初始是0（全局check的默认值），会导致min_element误选到这些无效索引，访问V[ind]时ind>=n，直接触发段错误！

把check改成局部的后，范围就变成check.begin(), check.end()刚好是n个元素，就不会有这个问题了。

6. 内存泄漏（非段错误但必须修复） #

动态分配的arr在函数结束后没有释放，会导致内存泄漏。记得在函数末尾释放：

for (i = 0; i < n; i++) {
    delete[] arr[i];
}
delete[] arr;

修复后的完整代码 #

#include <iostream>
#include <vector>
#include <algorithm>

#define INF 99999
typedef long int ull;

void prim(ull in, std::vector<std::vector<ull>>& V, ull** arr, std::vector<bool>& visit, std::vector<ull>& check) {
    ull i;
    visit[in] = true;
    for (i = 0; i < V[in].size(); i++) {
        ull neighbor = V[in][i];
        if (!visit[neighbor]) {
            check[neighbor] = std::min(check[neighbor], arr[in][neighbor]);
        }
    }
    check[in] = INF; // 标记为已处理，避免再次被选中
}

void solve() {
    ull i, n, e, s, u, v, w;
    std::cin >> n >> e;

    // 动态初始化所有容器，大小为n
    std::vector<std::vector<ull>> V(n);
    std::vector<bool> visit(n, false);
    std::vector<ull> check(n, INF);

    // 初始化二维数组并填充INF
    ull** arr = new ull*[n];
    for (i = 0; i < n; i++) {
        arr[i] = new ull[n];
        std::fill(arr[i], arr[i] + n, INF);
    }

    for (i = 0; i < e; i++) {
        std::cin >> u >> v >> w;
        u--;
        v--;
        arr[u][v] = w;
        arr[v][u] = w;
        V[u].push_back(v);
        V[v].push_back(u);
    }

    std::cin >> s;
    s--;
    check[s] = 0;

    ull ad = 0;
    for (i = 0; i < n; i++) {
        auto it = std::min_element(check.begin(), check.end());
        ull ind = it - check.begin();
        ad += *it;
        prim(ind, V, arr, visit, check);
    }

    std::cout << ad << "\n";

    // 释放动态内存
    for (i = 0; i < n; i++) {
        delete[] arr[i];
    }
    delete[] arr;
}

int main() {
    solve();
    return 0;
}

额外说明 #

• 我把prim函数的参数改成了引用传递，避免拷贝大容器，提高效率。
• 给变量加了更清晰的命名，比如neighbor，方便阅读。
• 确保所有容器的大小都和输入的节点数n一致，彻底避免越界问题。

内容的提问来源于stack exchange，提问作者low key