普利姆算法 （加点法）

普利姆算法 （加点法）

• 1. 任选一个点作为起点
• 2. 找到以当前选中点为起点路径最短的边
• 3. 如果这个边的另一端没有被联通进来，那么就连结
• 4. 如果这个边的另一端也早就被连进来了，则看倒数第二短的边
• 5. 重复 2- 4 直到将所有的点都连通为止。

// 希望将所有的村庄都联通，但是需要花费的钱最少 （A,B,C,D,E） 之间如何连接花费最少

最小花费连接：

// 代码实现


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 getIndex(str) {
    for(let i in pointSet){
        if(pointSet[i].value == str){
            return i;
        }
    }
    return -1;
}



// 需要传入点的集合，边的集合，当前已经连结进入的集合
// 此方法，根据当前已经有的节点，来进行判断，获取到距离最短的点
function getMinDisNode(pointSet, distance, nowPointSet) {
    let fromNode = null; //线段的起点
    let minDisNode = null; //线段的终点
    let minDis = max;
    // 根据当前已有的这些点为起点，依次判断连结其他的点的距离是多少
    for (let i = 0; i < nowPointSet.length; i++) {
        let nowPointIndex = getIndex(nowPointSet[i].value); // 获取当前节点的序号
        for (let j = 0; j < distance[nowPointIndex].length; j++) {
            let thisNode = pointSet[j]; // thisNode 表示 distance 中的点，但是这个点不是对象
            /* 首先这个点不能是已经接入的点, 其次 点之间的距离的是目前的最短距离 */
            if (nowPointSet.indexOf(thisNode) < 0 && distance[nowPointIndex][j] < minDis ) {
                fromNode = nowPointSet[i];
                minDisNode = thisNode;
                minDis = distance[nowPointIndex][j];
            }
        }
    }
    fromNode.neighbor.push(minDisNode);
    minDisNode.neighbor.push(fromNode);
    return minDisNode;
}

function prim(pointSet, distance, start) {
    let nowPointSet = [];
    nowPointSet.push(start);
    // 获取最小代价的边
    while (true) {
        let minDisNode = getMinDisNode(pointSet, distance, nowPointSet);
        nowPointSet.push(minDisNode);
        if(nowPointSet.length == pointSet.length){
            break;
        }
    }
}

prim(pointSet, distance, c);

console.log(pointSet);