什么是Kruskal算法
最小生成树是一个图的极小连通子图,它包含原图的所有顶点,并且所有边的权值之和尽可能小。
之前描述了Prim算法是用于生成图结构的最小生成树,而Kruskal算法(中文名:克鲁斯卡尔算法),是另外一种最小生成树算法,用的也是贪婪算法的思想。
Kruskal算法详细解析
以下算法详细步骤图,均来自B站up主"WAY_zhong"的视频——《最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示》
最小生成树既然是树,则需要遵循树的以下几个规则:
1.因为是树的结构,所有结构中不能形成环。
2.必须连接图结构中的所有顶点,任意两个顶点间都是互通的。
3.如果树有n个顶点,它对应边的个数就是n-1个。
假如有这样一个无向带权图
接着把图实例中所有的边取出,放到一个列表中
并按照边的权值,由小到大进行排列
接着在列表中按次序,每次取出一条边,回添到图实例中,不断重复此过程……
每次添加一条边,都判断是否形成了环(形成了环),如果如果没有形成环,那么这个条边就会被选中,成为最小生成树的一条边。
相反,如果形成了环,这条边则会被抛弃,接着判断列表中的下一条边
直到选择了n-1条边(满足树对边的规则),其中n是顶点的个数,此时最小生成树完成。
完整可视化算法流程可参考B站原作者的视频:
最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示
代码实现
// INF常量保存Number类型的无穷大
const INF = Number.MAX_SAFE_INTEGER;
/**
* 检查 MST(最小生成树) 中是否已存在这条边,以避免环路(查找连接顶点的尾部下标)
* @param {*} i 需要检查的边(连线开始的顶点)
* @param {*} parent 图实例对应的最小生成树的数组(判断边与边是否形成环路的数组)
* @returns {*} 返回找到的边
* */
const find = (i, parent) => {
while (parent[i]) { // 如果在最小生成树的数组存在,则把值交给i
i = parent[i]; // eslint-disable-line prefer-destructuring
}
return i; // 将找到的边返回
};
/**
* 检查 MST(最小生成树) 的边是否相同
* @param {*} i 需要检查的边i
* @param {*} j 需要检查的边j
* @param {*} parent 图实例对应的最小生成树的数组
* @returns {*} 返回边是否相等,true为不相同,false为相同
* */
const union = (i, j, parent) => {
// 判断两个节点是否在同一颗树中,即是否相交
if (i !== j) { // 如果i和j是不同的边,说明此边没有与现有生成树形成环路,则将他们加入最小生成树(MST)
parent[j] = i; // j为父亲节点,i为边权值
return true;
}
return false;
};
/**
* 对整个图进行拷贝并初始化权值的内部函数
* @param {*} graph 图实例
* @returns {*} 返回拷贝且初始化权值后的图实例
* */
const initializeCost = graph => {
const cost = [];
const { length } = graph;
for (let i = 0; i < length; i++) {
cost[i] = [];
for (let j = 0; j < length; j++) {
if (graph[i][j] === 0) {
cost[i][j] = INF;
} else {
cost[i][j] = graph[i][j];
}
}
}
return cost;
};
/**
* 最小生成树算法-kruskal算法
* @param {*} graph 需要计算最小生成树的图实例
* @returns {*} 图实例的最小生成树
*/
export const kruskal = graph => {
const { length } = graph; //图实例的顶点数量
const parent = []; //创建最小生成树数组(用一维数组来表达最小生成树,数组下标所对应的元素,代表该顶点在最小生成树当中的父亲节点)
let ne = 0; // 最小生成树的边数
let a;
let b;
let u;
let v;
const cost = initializeCost(graph); // 首先,把邻接矩阵的值复制到 cost 数组,以方便修改且可以保留原始值行
while (ne < length - 1) { // 当 MST(最小生成树) 的边数小于顶点总数减 1 时(对于有n个顶点的树,它的边是它的顶点总数-1)
// 找出权值最小的边
for (let i = 0, min = INF; i < length; i++) { //遍历图的所有顶点,初始化当前最小的权值-min(默认为无穷大)
for (let j = 0; j < length; j++) { // 遍历当前顶点的邻接矩阵
if (cost[i][j] < min) { // 如果当前遍历的边权重小于目前记录的最小边(min)
min = cost[i][j]; // 更新目前记录的最小权值
a = u = i; // a和u记录当前所存储的最小边的起始顶点
b = v = j; // b和v记录当前所存储的最小边的到达顶点
}
}
}
u = find(u, parent); // 通过下标(也就是父亲节点)检查 MST(最小生成树) 中是否已存在这条边,以避免环路
v = find(v, parent); // 通过下标(也就是父亲节点)检查 MST(最小生成树) 中是否已存在这条边,以避免环路
if (union(u, v, parent)) { // 如果 u 和 v 是不同的边(不同的父亲节点,没有形成环路),则将其加入 MST(最小生成树)
ne++; // 最小生成树的边数
}
cost[a][b] = cost[b][a] = INF; // 从列表中移除这些边,以免重复计算
}
// 返回MST(最小生成树)
return parent;
};