算法

克鲁斯卡尔算法（加边法）

updated on
  • 1. 选择最短的边进行连结
  • 2. 要保证边连结的两端至少有一个点事最新的点
  • 3. 或者 这个边是将两个部落进行连结的
  • 4. 重复 1- 3 直到将所有的点都连结到一起
// 代码实现


let max = 1000000;
let pointSet = [];
let distance = [
    [0, 4, 7, max, max],
    [4, 0, 8, 6, max],
    [7, 8, 0, 5, max],
    [max, 6, 5, 0, 7],
    [max, max, max, 7, 0]
]

function Node(value) {
    this.value = value;
    this.neighbor = [];
}

let a = new Node("A");
let b = new Node("B");
let c = new Node("C");
let d = new Node("D");
let e = new Node("E");

pointSet.push(a);
pointSet.push(b);
pointSet.push(c);
pointSet.push(d);
pointSet.push(e);


function canLink(resultList, tmpBegin, tmpEnd) {
    let beginIn = null;
    let endIn = null;
    for(let i=0; i< resultList.length; i++){
        if(resultList[i].indexOf(tmpBegin) > -1){
            beginIn = resultList[i];
        }
        if(resultList[i].indexOf(tmpEnd) > -1){
            endIn = resultList[i];
        }
    }
    // 两个点都是新的点（都不在任何部落里）--- 可以连接，产生新的部落
    // begin 在A部落，end没有部落 --- A 部落扩张一个村庄
    // end 在A部落，begin没有部落 --- A 部落扩张一个村庄
    // begin 在 A 部落，end 在 B 部落 --- 将 AB 两个部落合并
    // begin 和 end 在同一个部落 --- 不可以连接
    if(beginIn != null && endIn != null && beginIn == endIn){
        return false;
    }
    return true;
}

function link(resultList, tmpBegin, tmpEnd) {
    let beginIn = null;
    let endIn = null;
    for(let i=0; i< resultList.length; i++){
        if(resultList[i].indexOf(tmpBegin) > -1){
            beginIn = resultList[i];
        }
        if(resultList[i].indexOf(tmpEnd) > -1){
            endIn = resultList[i];
        }
    }
    
    if(beginIn == null && endIn == null){   // 两个点都是新的点（都不在任何部落里）--- 可以连接，产生新的部落
        let newArr = [];
        newArr.push(tmpBegin);
        newArr.push(tmpEnd);
        resultList.push(newArr);
    }else if(beginIn != null && endIn == null){ // begin 在A部落，end没有部落 --- A 部落扩张一个村庄
        beginIn.push(tmpEnd);
    }else if(beginIn == null && endIn != null){ // end 在A部落，begin没有部落 --- A 部落扩张一个村庄
        endIn.push(tmpBegin);
    }else if(beginIn != null && endIn != null && beginIn != endIn){ // begin 在 A 部落，end 在 B 部落 --- 将 AB 两个部落合并
        let allIn = beginIn.concat(endIn);
        let needRemove = resultList.indexOf(endIn);
        resultList.splice(needRemove, 1);
        needBeginRemove = resultList.indexOf(beginIn);
        resultList.splice(needBeginRemove, 1);
        resultList.push(allIn);
    }
    tmpBegin.neighbor.push(tmpEnd);
    tmpEnd.neighbor.push(tmpBegin);
}

function kruskal(pointSet, distance) {
    let resultList = []; // 二维数组，此数组代表的是有多少个"部落"
    while (true) {
        let minDis = max;
        let begin = null;
        let end = null;
        for (let i = 0; i < distance.length; i++) {
            for (let j = 0; j < distance[i].length; j++) {
                let tmpBegin = pointSet[i];
                let tmpEnd = pointSet[j];
                /* 去掉自己到自己的距离，因为都为0 */
                if (i != j && distance[i][j] < minDis && canLink(resultList, tmpBegin, tmpEnd)) {
                    minDis = distance[i][j];
                    begin = tmpBegin;
                    end = tmpEnd;
                }
            }
        }
        link(resultList, begin, end);
        if (resultList.length == 1 && resultList[0].length == pointSet.length) { // 只存在一个部落
            break;
        }
    }
}

kruskal(pointSet, distance);

console.log(pointSet);

其他内容