C语言实现Kruskal算法时min-heap动态分配容量上限问题咨询

一、内存分配疑问解答 #

不需要预先分配50000000个edge的内存，按照实际输入边数ne动态分配是更合理的方案，理由如下：

• 单个edge结构体占12字节（3个int变量），5000万条边占约600MB内存，若输入边数远小于上限，预分配会造成极大的内存浪费
• 只要做好两个前置校验，动态分配完全可以在5000万边的场景下正常运行：
  1. 读取ne后先校验是否不超过你定义的maxedge上限
  2. 调用malloc后检查返回值是否为NULL，避免内存分配失败导致程序崩溃

修改参考代码：

// 读取nv、ne后新增校验逻辑
if (nv > maxvertice || ne > maxedge) {
    printf("输入的顶点数/边数超出支持上限\n");
    fclose(fp);
    fclose(result);
    return 0;
}
parent = (int*)malloc(sizeof(int)*nv);
minheap = (edge*)malloc(sizeof(edge)*ne);
// 检查内存分配是否成功
if (parent == NULL || minheap == NULL) {
    printf("内存分配失败\n");
    if (parent) free(parent);
    if (minheap) free(minheap);
    fclose(fp);
    fclose(result);
    return 0;
}

二、现有代码优化建议 #

• 并查集性能优化：当前的findparent没有路径压缩、makeunion没有按秩合并，大数据量下性能损耗非常明显，修改后并查集操作几乎为常数时间：

  // 新增rank数组，和parent一起初始化，初始值全为1
  int *rank;
  // 带路径压缩的find
  int findparent(int i) {
      if (parent[i] != i) parent[i] = findparent(parent[i]);
      return parent[i];
  }
  // 按秩合并的union
  void makeunion(int x, int y) {
      x = findparent(x);
      y = findparent(y);
      if (x == y) return;
      if (rank[x] < rank[y]) {
          parent[x] = y;
      } else {
          parent[y] = x;
          if (rank[x] == rank[y]) rank[x]++;
      }
  }
  

• 排序效率优化：目前逐个插入堆的排序效率低于标准库的qsort函数，5000万条边的场景下差距可达数倍，建议先把所有边读入数组，直接用qsort排序代替自行实现的堆结构。
• 输入效率优化：fscanf读取5000万条边的速度很慢，建议给输入文件设置大缓冲区提升IO效率：

  setvbuf(fp, NULL, _IOFBF, 1 << 24); // 设置16MB的全缓冲
  

• 溢出风险修复：当前sumofweight用int类型存储，当权重较大、边数较多时会发生整数溢出，建议修改为long long sumofweight = 0，输出时用%lld格式化。
• 边界逻辑优化：当选中边数达到nv-1后直接终止循环即可，不需要遍历剩余所有边，可进一步节省运行时间。

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