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; }