普利姆演算法（加點法）求最小生成樹 <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> ...
普利姆演算法（加點法）求最小生成樹
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function Node(value) {
this.value = value;
this.neighbor = [];
this.distance = [];
}
var nodeA = new Node("a");
var nodeB = new Node("b");
var nodeC = new Node("c");
var nodeD = new Node("d");
var nodeE = new Node("e");
var nodeF = new Node("f");
var nodeG = new Node("g");
var nodeH = new Node("h");
//存放所有節點的數組
var pointSet = [nodeA, nodeB, nodeC, nodeD, nodeE, nodeF, nodeG, nodeH];
var max = Number.POSITIVE_INFINITY; //無窮大
var distance = [ //點與點之間的距離
// a b c d e f g h
[0, 1, 2, max, max, max, max, max], //a
[1, 0, max, 3, max, 5, max, max], //b
[2, max, 0, 4, max, max, 7, max], //c
[max, 3, 4, 0, 6, max, max, max], //d
[max, max, max, 6, 0, 8, 9, max], //e
[max, 5, max, max, 8, 0, max, 10], //f
[max, max, 7, max, 9, max, 0, 11], //g
[max, max, max, max, max, 10, 11, 0] //h
];
//prim演算法
function prim(pointSet, distance, start) {
var nowPointSet = [];
nowPointSet.push(start);//將開始節點放入已連接數組中
while (true) {
//通過已連接節點，找到和它們相連接開銷最小的節點
var minDistanceNode = getMinDistanceNode(pointSet, distance, nowPointSet);
nowPointSet.push(minDistanceNode);//將開銷最小的節點加入已連接數組中
if(nowPointSet.length == pointSet.length) break;//所有節點都連接，跳出迴圈
}
console.log(nowPointSet);
}
function getMinDistanceNode(pointSet, distance, nowPointSet) {
for (var i = 0; i < nowPointSet.length; i++) { //遍歷已連接的點
var pointIndex = getIndex(nowPointSet[i].value);//獲取已連接節點在pointSet中的索引值
var pointDistance = distance[pointIndex];//通過pointIndex找到該連接節點對應所有邊的開銷
var minDistance = max;//最小距離預設為max
var fromNode = null;//起始節點
var endNode = null;//終止節點
for (var j = 0; j < pointDistance.length; j++) { //遍歷所有邊的開銷
if (nowPointSet.indexOf(pointSet[j]) < 0 && pointDistance[j] <
minDistance) { //最小距離連接的節點不能在nowPointSet中 && 要小於minDistance
minDistance = pointDistance[j];
fromNode = nowPointSet[i];
endNode = pointSet[j];
}
}
}
fromNode.neighbor.push(endNode);//起始節點 將開銷最小的節點加入
fromNode.distance.push({//起始節點 將開銷最小的節點的值和距離加入
from: fromNode.value,
to: endNode.value,
distance: minDistance
});
endNode.neighbor.push(fromNode);
endNode.distance.push({
from: fromNode.value,
to: endNode.value,
distance: minDistance
});
return endNode;//返回開銷最小的節點
}
function getIndex(str) {//獲取索引值
for (var i = 0; i < pointSet.length; i++) {
if (str == pointSet[i].value) {
return i;
}
}
return -1;
}
prim(pointSet, distance, pointSet[2]);
</script>
</body>
</html>
普利姆演算法
