题解 | #最小生成树#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 返回最小的花费代价使得这n户人家连接起来
 * @param n int整型 n户人家的村庄
 * @param m int整型 m条路
 * @param cost int整型二维数组 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
 * @return int整型
 */
function miniSpanningTree( n ,  m ,  cost ) {
    // write code here
    // 按照权重排序
    cost.sort((a,b) => a[2]-b[2]);
    let parentArr = [];
    // 初始化父节点
    for(let i = 0; i < n; i++) {
        parentArr[i] = -1;
    }

    // 获取父节点
    const setParent = (i) => {
        if(parentArr[i] !== -1) {
            return parentArr[i];
        }
        return i;
    }

    // 是否成环
    const ifCircle = (startParentIndex,endParentIndex) => {
        if(startParentIndex !== endParentIndex) {
            // 正常处理线的2个顶点为并查集
            parentArr[endParentIndex] = startParentIndex;
            
            // 如果存在多个endParentIndex为父节点的节点处理
            let indexArr = [];
            for(index in parentArr) {
                if(parentArr[index] === endParentIndex) {
                    indexArr.push(index);
                }
            }
            indexArr.forEach(index => parentArr[index] = startParentIndex);
            return false;
        }else {
            return true;
        }
    }

    // 实现获取最短路径的算法
    let res = []
    for(let i = 0; i < cost.length; i++) {
        let startIndex = cost[i][0]-1;
        let endIndex = cost[i][1]-1;

        let startParentIndex = setParent(startIndex);
        let endParentIndex = setParent(endIndex);

        if(!ifCircle(startParentIndex, endParentIndex)) {
            res.push(cost[i])
        }
    }
    console.log(res);
    return res.map(v => v[2]).reduce((a,b) => a + b, 0);
}
module.exports = {
    miniSpanningTree : miniSpanningTree
};