Kruskal算法和Prim算法构造它的一棵最小代价生成树的过程
发布网友
发布时间：2022-05-15 00:14
共3个回答
懂视网
时间：2022-04-26 22:41
之前都是看书，大部分也是c++的实现，但是搞前端不能忘了JS啊，所以JS实现一遍这两个经典的最小生成树算法。
一、权重图和最小生成树
权重图：图的边带权重
最小生成树：在连通图的所有生成树中，所有边的权重和最小的生成树
本文使用的图如下：
它的最小生成树如下：
二、邻接矩阵
邻接矩阵：用来表示图的矩阵就是邻接矩阵，其中下标表示顶点，矩阵中的值表示边的权重（或者有无边，方向等）。
本文在构建邻接矩阵时，默认Number.MAX_SAFE_INTEGER表示两个节点之间没有边，Number.MIN_SAFE_INTEGER表示当前节点没有自环。
代码如下：
/** * 邻接矩阵 * 值为顶点与顶点之间边的权值，0表示无自环，一个大数表示无边(比如10000) * */ const MAX_INTEGER = Number.MAX_SAFE_INTEGER;//没有的边 const MIN_INTEGER = Number.MIN_SAFE_INTEGER;//没有自环 const matrix= [ [MIN_INTEGER, 9, 2, MAX_INTEGER, 6], [9, MIN_INTEGER, 3, MAX_INTEGER, MAX_INTEGER], [2, 3, MIN_INTEGER, 5, MAX_INTEGER], [MAX_INTEGER, MAX_INTEGER, 5, MIN_INTEGER, 1], [6, MAX_INTEGER, MAX_INTEGER, 1, MIN_INTEGER] ];
这个邻接矩阵表示的图如下：
三、 边的表示
一个边具有权重、起点、重点三个属性，所以可以创建一个类(对象)，实现如下：
/**
* 边对象
* */
function Edge(begin, end, weight) {
this.begin = begin;
this.end = end;
this.weight = weight;
}
Edge.prototype.getBegin = function () {
return this.begin;
};
Edge.prototype.getEnd = function () {
return this.end;
};
Edge.prototype.getWeight = function () {
return this.weight;
};
/*class Edge {
constructor(begin, end, weight) {
this.begin = begin;
this.end = end;
this.weight = weight;
}
getBegin() {
return this.begin;
}
getEnd() {
return this.end;
}
getWeight() {
return this.weight;
}
}*/
PS：JS这门语言没有私有变量的说法，这里写get方法纯粹是模拟一下私有变量。可以不用这么写，可以直接通过属性访问到属性值。
四、Prim算法
将这个算法的文章数不胜数，这里就不细说了。
其大体思路就是：以某顶点为起点，逐步找各顶点上最小权值的相邻边构建最小生成树，同时其邻接点纳入生成树的顶点中,只要保证顶点不重复添加即可。
实现代码如下：
/**
* Prim算法
* 以某顶点为起点，逐步找各顶点上最小权值的边构建最小生成树，同时其邻接点纳入生成树的顶点中,只要保证顶点不重复添加即可
* 使用邻接矩阵即可
* 优点：适合点少边多的情况
* @param matrix 邻接矩阵
* @return Array 最小生成树的边集数组
* */
function prim(matrix) {
const rows = matrix.length,
cols = rows,
result = [],
savedNode = [0];//已选择的节点
let minVex = -1,
minWeight = MAX_INTEGER;
for (let i = 0; i < rows; i++) {
let row = savedNode[i],
edgeArr = matrix[row];
for (let j = 0; j < cols; j++) {
if (edgeArr[j] < minWeight && edgeArr[j] !== MIN_INTEGER) {
minWeight = edgeArr[j];
minVex = j;
}
}
//保证所有已保存节点的相邻边都遍历到
if (savedNode.indexOf(minVex) === -1 && i === savedNode.length - 1) {
savedNode.push(minVex);
result.push(new Edge(row, minVex, minWeight));
//重新在已加入的节点集中找权值最小的边的外部边
i = -1;
minWeight = MAX_INTEGER;
//已加入的边，去掉，下次就不会选这条边了
matrix[row][minVex] = MAX_INTEGER;
matrix[minVex][row] = MAX_INTEGER;
}
}
return result;
}
五、Kruskal算法
介绍这个算法的文章也很多，这里不细说。
其主要的思路就是：遍历所有的边，按权值从小到大排序，每次选取当前权值最小的边，只要不构成回环，则加入生成树。
5.1 邻接矩阵转成边集数组
与Prim算法不同，Kruskal算法是从最小权值的边开始的，所以使用边集数组更方便。所以需要将邻接矩阵转成边集数组，并且按照边的权重从小到大排序。
/**
* 邻接矩阵转边集数组的函数
* @param matrix 邻接矩阵
* @return Array 边集数组
* */
function changeMatrixToEdgeArray(matrix) {
const rows = matrix.length,
cols = rows,
result = [];
for (let i = 0; i < rows; i++) {
const row = matrix[i];
for(let j = 0 ; j < cols; j++) {
if(row[j] !== MIN_INTEGER && row[j] !== MAX_INTEGER) {
result.push(new Edge(i, j, row[j]));
matrix[i][j] = MAX_INTEGER;
matrix[j][i] = MAX_INTEGER;
}
}
}
result.sort((a, b) => a.getWeight() - b.getWeight());
return result;
}
5.2 Kruskal算法的具体实现
Kruskal算法的一个要点就是避免环路，这里采用一个数组来保存已纳入生成树的顶点和边（连线），其下标是边（连线）的起点，下标对应的元素值是边（连线）的终点。下标对应的元素值为0，表示还没有以它为起点的边（连线）。
连线：表示一条或多条边前后连接形成的一条线，这条线没有环路。
/**
* kruskal算法
* 遍历所有的边，按权值从小到大排序，每次选取当前权值最小的边，只要不构成回环，则加入生成树
* 邻接矩阵转换成边集数组
* 优点：适合点多边少的情况
* @param matrix 邻接矩阵
* @return Array 最小生成树的边集数组
* */
function kruskal(matrix) {
const edgeArray = changeMatrixToEdgeArray(matrix),
result = [],
//使用一个数组保存当前顶点的边的终点,0表示还没有已它为起点的边加入
savedEdge = new Array(matrix.length).fill(0);
for (let i = 0, len = edgeArray.length; i < len; i++) {
const edge = edgeArray[i];
const n = findEnd(savedEdge, edge.getBegin());
const m = findEnd(savedEdge, edge.getEnd());
console.log(savedEdge, n, m);
//不相等表示这条边没有与现有生成树形成环路
if (n !== m) {
result.push(edge);
//将这条边的结尾顶点加入数组中，表示顶点已在生成树中
savedEdge[n] = m;
}
}
return result;
}
/**
* 查找连线顶点的尾部下标
* @param arr 判断边与边是否形成环路的数组
* @param start 连线开始的顶点
* @return Number 连线顶点的尾部下标
* */
function findEnd(arr, start) {
//就是一直循环，直到找到终点，如果没有连线，就返回0
while (arr[start] > 0) {
start = arr[start];
}
return start;
}
热心网友
时间：2022-04-26 19:49
算法思想：假设N={V,{E}}是连通网，TE是N上最小生成树中边的集合。算法从U={u0},TE ={}开始，重复执行下述操作：在所有u∈U,v∈V-U的边（u，v）∈E中找一条代价最小的边（u0,v0）并入集合TE，同时v0并入U，直至U=V为止。
Kruskal算法复杂度：O(eloge)，相对于Prim而言，适合求边稀疏的网的最小生成树。
算法思想：最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去次边而选择下一条代价最小的边。直至T中所有顶点都在同一连通分量上为止。
热心网友
时间：2022-04-26 21:07
其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。
与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。
复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}
