9.普利姆演算法（加點法）求最小生成樹（JavaScript版）-有解無憂

普利姆演算法（加點法）求最小生成樹
<!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
        ];

        //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>
普利姆演算法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/55598.html
標籤：JavaScript
上一篇：vue~父組件與子組件的互動
下一篇：JS-多組關鍵詞串列高亮