克魯斯卡爾演算法求最小生成樹：
<!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 =https://www.cnblogs.com/lanshanxiao/p/ 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
];
//克魯斯卡爾演算法
function kurskal(pointSet, distance) {
var resultList = []; //這是一個二維陣列，用來存放已連接的部落
while (true) {
var begin = null;
var end = null;
var minDistance = max;
for (var i = 0; i < distance.length; i++) {
for (var j = 0; j < distance[i].length; j++) {
var tempBegin = pointSet[i];
var tempEnd = pointSet[j];
if (i != j && //自己到自己的距離為0,不能加入
distance[i][j] < minDistance && //當前開銷小于最小開銷
canLink(tempBegin, tempEnd, resultList)) { //判斷節點是否可以連接
begin = tempBegin;
end = tempEnd;
minDistance = distance[i][j];
}
}
}
link(begin, end, resultList, minDistance); //將最小開銷加入
if (resultList.length == 1 && resultList[0].length == pointSet.length) { //當結果中只有一個部落 && 部落中節點數等于點集合數
break;
}
}
console.log(pointSet);
}
function canLink(begin, end, resultList) { //判斷節點是否可以連接
var beginIn = null; //存放begin所在的部落
var endIn = null; //存放end所在的部落
for (var i = 0; i < resultList.length; i++) { //回圈所有部落
if (resultList[i].indexOf(begin) > -1) { //找到begin所在的部落
beginIn = resultList[i];
}
if (resultList[i].indexOf(end) > -1) { //找到end所在的部落
endIn = resultList[i];
}
}
//1.begin和end都不在部落中----兩者可以加入新部落
//2.begin在A部落，end不在部落中----A部落擴張一個節點
//3.begin不在部落，end在A部落中----A部落擴張一個節點
//4.begin在A部落，end在B部落----A和B兩個部落可以合并
//5.begin和end在同一個部落----不能連接
if (beginIn != null && endIn != null && beginIn == endIn) {
return false; //滿足第5個條件
}
return true; //其他條件都是可連接的
}
function link(begin, end, resultList, minDistance) { //把節點加入部落
var beginIn = null; //存放begin所在的部落
var endIn = null; //存放end所在的部落
for (var i = 0; i < resultList.length; i++) { //回圈所有部落
if (resultList[i].indexOf(begin) > -1) { //找到begin所在的部落
beginIn = resultList[i];
}
if (resultList[i].indexOf(end) > -1) { //找到end所在的部落
endIn = resultList[i];
}
}
//1.begin和end都不在部落中----兩者可以加入新部落
if (beginIn == null && endIn == null) {
var newArr = [];
newArr.push(begin);
newArr.push(end);
resultList.push(newArr);
} else if (beginIn != null && endIn == null) { //2.begin在A部落，end不在部落中----A部落擴張一個節點
beginIn.push(end);
} else if (beginIn == null && endIn != null) { //3.begin不在部落，end在A部落中----A部落擴張一個節點
endIn.push(begin);
} else if (beginIn != null && endIn != null) { //4.begin在A部落，end在B部落----A和B兩個部落可以合并
beginIn.concat(endIn);
resultList.slice(resultList.indexOf(endIn), 1); //去除endIn部落
}
begin.neighbor.push(end);
begin.distance.push({
from: begin,
to: end,
distance: minDistance
});
end.neighbor.push(begin);
end.distance.push({
from: end,
to: begin,
distance: minDistance
});
}
kurskal(pointSet, distance);
</script>
</body>
</html>
克魯斯卡爾演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38874.html
標籤：其他
上一篇：網路小白求幫忙
下一篇：思科路由重分發