Kruskal Algorithm实现大输入时错误码3221225477崩溃问题排查

异常根因 #

退出码3221225477是Windows平台下的内存访问违例错误，对应Linux平台的段错误，触发原因如下：

• 数组越界访问（最高概率）：代码中定义MAX_VERTICES = 10000，并查集数组parent_array仅分配了10000个元素空间，如果大体积输入的顶点编号≥10000，或是顶点总数超过10000，访问parent_array[i]时会直接越界，触发内存访问错误。
• 大内存分配失败：全局数组min_heap[MAX_EDGES]预先分配了5000万个元素空间，单个element结构体占用12字节，总大小约600MB。如果是32位编译模式，用户态虚拟地址空间仅2GB，很容易出现静态存储区分配不足，运行时访问堆数组越界。
• 循环逻辑缺陷：当前循环执行顺序为「提前删除一次堆顶→循环处理当前边→末尾再删除堆顶」，当堆已经为空（n_heap=0）时，仍会调用delete_min_heap，触发堆空退出逻辑，但由于stderr缓冲区未刷新，你看不到报错提示就会程序退出。
• 输入读取逻辑缺陷：使用feof作为文件结束判断条件，会多读取最后一行空内容，此时strtok返回NULL，atoi(NULL)会触发未定义行为，大概率导致崩溃。

修复方案 #

1. 调整内存分配逻辑，避免静态大数组越界 #

将静态数组改为动态分配，读取到输入的顶点数、边数后再分配对应大小的空间，避免空间浪费和越界：

// 删除原来的全局数组定义，改为指针声明
element *min_heap;
int *parent_array;
#define HEAP_FULL(n, max) (n == max-1) // 修改堆满判断宏，适配动态大小

在读取输入时动态分配空间：

else if(line_num == 0) {
    num_vertices = atoi(buffer);
    // 分配并查集数组，多留冗余避免顶点号超界
    parent_array = malloc(sizeof(int) * (num_vertices + 10));
    if(!parent_array) { perror("并查集数组分配失败"); exit(1); }
}
else if(line_num == 1) {
    num_edges = atoi(buffer);
    // 堆下标从1开始，多分配1个元素空间
    min_heap = malloc(sizeof(element) * (num_edges + 1));
    if(!min_heap) { perror("堆数组分配失败"); exit(1); }
}

同时建议编译时选择64位模式，避免32位地址空间不足。

2. 修复循环逻辑，避免堆空仍调用删除接口 #

调整循环执行顺序，将删除堆顶操作移到循环开头，堆空时直接终止循环：

// 删除进入循环前的delete_min_heap调用
int j = 0;
cost = 0;
n_connected = 0;
while(n_heap > 0 && n_connected != num_vertices) {
    element edge = delete_min_heap(&n_heap);
    int node1 = edge.node1;
    int node2 = edge.node2;
    if(j == 0)  {
        weightedUnion(node1, node2);
        cost += edge.weight;
        n_connected += 2;
        j++;
    }
    else if (simpleFind(node1) != simpleFind(node2)) {
        weightedUnion(node1, node2);
        cost += edge.weight;
        n_connected++;
    }
    printf("%d %d\n", n_connected, n_heap);
}

3. 修复输入读取逻辑 #

替换feof判断，改为直接判断fgets返回值，同时对strtok结果做判空处理，避免空行崩溃：

while (fgets(buffer, sizeof(buffer), fp1) != NULL) {
    if(line_num == 0) {
        num_vertices = atoi(buffer);
        parent_array = malloc(sizeof(int) * (num_vertices + 10));
        if(!parent_array) { perror("并查集数组分配失败"); exit(1); }
    }
    else if(line_num == 1) {
        num_edges = atoi(buffer);
        min_heap = malloc(sizeof(element) * (num_edges + 1));
        if(!min_heap) { perror("堆数组分配失败"); exit(1); }
    }
    else {
        char *p1 = strtok(buffer, " \t\n");
        char *p2 = strtok(NULL, " \t\n");
        char *p3 = strtok(NULL, " \t\n");
        // 跳过空行、格式错误行
        if(!p1 || !p2 || !p3) continue;
        int vertex_from = atoi(p1);
        int vertex_to = atoi(p2);
        int weight = atoi(p3);
        element edge = {weight, vertex_from, vertex_to};
        insert_min_heap(edge, &n_heap, num_edges); // 插入时传入最大边数判断堆满
    }
    line_num++;
}

额外优化 #

给simpleFind函数添加路径压缩逻辑，大输入下并查集查询效率会提升数倍：

int simpleFind(int i) {
    int root = i;
    for( ; parent_array[root] >= 0; root = parent_array[root]);
    // 路径压缩
    while(i != root) {
        int next = parent_array[i];
        parent_array[i] = root;
        i = next;
    }
    return root;
}

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