Menu
CoddyTech

实现(第 2 部分)

Coddy 克鲁斯卡尔算法:图算法 课程的第 6 课,共 9 课。

现在继续添加最便宜的安全边,直到 MST 完成为止。

challenge icon

挑战

中等

现在来构建最小生成树。

编写一个名为 kruskal 的函数,它接收 n 和连通图的扁平 edges 数组(由三元组组成,表示无向边),并返回其最小生成树的总权重。

重复选取尚未使用的最小权重边。如果这条边的两个端点属于不同的集合,就合并这两个集合并加上这条边的权重;否则跳过这条边。

重用上一课中的并查集思路。

亲手试试

#include <stdlib.h>

int kruskal(int n, int* edges, int edges_size) {
    // 在这里编写代码
    return 0;
}
quiz icon自我测试

这节课包含一个小测验。开始学习即可作答,并记录你的进度。

克鲁斯卡尔算法:图算法中的所有课

自己练习: C 在线编译器