Minimum Span Tree/PrimMinIndexHeap.html

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script src="../Graph%20Theory/Edge.js"></script>
<script>
    //思路：利用最小索引堆，分为3个步骤：
    // 1、从源点(节点)开始计算寻找到所到点的权值
    // 2、如果已经过此点则继续寻找后一个最小的权值，没有则先查找到此点是否已经过，没有则继续判断是否已记录权值，有则比较大小，没有则记录到此点的最小权值
    // 3、利用最小堆推出最小权值，并记录这个权值所对应的点,对这个点重复步骤1
    class PrimMST {
        constructor(matrix) {
            this.rows = matrix.length;
            this.matrix = [];
            this.mst = [];
            this.marked = [];
            this.edgeTo = [];
            this.ipq = new IndexMinHeap(matrix.length);
            for (let i = 0; i < this.rows; i++) {
                this.marked[i] = false;
                this.edgeTo.push(0);
            }

            //初始化矩阵
            this.initMatrix(matrix);
            //构建最小生成树
            this.buildMST();
            console.log(this.mst)
        }

        initMatrix(matrix) {
            for (let i = 0; i < matrix.length; i++) {
                this.matrix[i] = [];
                for (let j = 0; j < matrix[i].length; j++) {
                    if (matrix[i][j]) {
                        this.matrix[i].push(new Edge(i, j, matrix[i][j]))
                    }
                }
            }
        }

        buildMST() {
            this.visit(0);
            while (!this.ipq.isEmpty()) {
                let v = this.ipq.extractMinIndex();
                this.mst.push(this.edgeTo[v]);
                this.visit(v)
            }
        }

        visit(v) {
            if (this.marked[v]) return;
            this.marked[v] = true;
            let e, w;
            for (let i = 0; i < this.matrix[v].length; i++) {
                e = this.matrix[v][i];
                w = e.other(v);
                if (!this.marked[w]) {
                    if (!this.edgeTo[w]) {
                        this.ipq.insert(w, e.wt());
                        this.edgeTo[w] = e;
                    } else if (e.wt() < this.edgeTo[w].wt()) {
                        this.edgeTo[w] = e;
                        this.ipq.change(w, e.wt());
                    }
                }
            }
        }
    }

    //region 最小索引堆
    class IndexMinHeap {
        constructor(capacity) {
            this.data = Array(capacity + 1);
            this.indexes = Array(capacity + 1);
            this.reverse = Array(capacity + 1).fill(0);
            this.count = 0;
            this.capacity = capacity;
        }

        insert(i, val) {
            if (this.count + 1 > this.capacity || !this.contain(i)) return;

            this.data[++i] = val;
            this.indexes[++this.count] = i;
            this.reverse[i] = this.count;
            this.shiftUp(this.count);

        }

        shiftUp(k) {
            while (k > 1 && this.data[this.indexes[k]] < this.data[this.indexes[k >> 1]]) {
                this.swapIndex(k, k >> 1);
                k = k >> 1;
            }
        }

        shiftDown(k) {
            while (k * 2 <= this.count) {
                let j = k * 2;
                if (j + 1 <= this.count && this.data[this.indexes[j + 1]] < this.data[this.indexes[j]]) {
                    j++
                }
                if (this.data[this.indexes[k]] < this.data[this.indexes[j]]) return;

                this.swapIndex(k, j)
                k = j
            }
        }

        contain(i) {
            return this.reverse[i + 1] === 0;
        }

        extractMin() {
            if (!this.count) return;

            let res = this.data[this.indexes[1]];
            this.swapIndex(1, this.count);
            this.reverse[this.indexes[this.count]] = 0;
            this.count--;
            this.shiftDown(1);
            return res

        }

        extractMinIndex() {
            if (!this.count) return;

            let res = this.indexes[1] - 1;
            this.swapIndex(1, this.count);
            this.reverse[this.indexes[this.count]] = 0;
            this.count--;
            this.shiftDown(1);
            return res
        }

        isEmpty() {
            return this.count === 0
        }

        swapIndex(i, j) {
            [this.indexes[i], this.indexes[j]] = [this.indexes[j], this.indexes[i]]

            this.reverse[this.indexes[i]] = i;
            this.reverse[this.indexes[j]] = j;
        }

        change(i, val) {
            i++;
            this.data[i] = val;

            this.shiftUp(this.reverse[i])
            this.shiftDown(this.reverse[i])
        }
    }
    //endregion

    const matrix = [
        [0, 0, 0.26, 0, 0.38, 0, 0.58, 0.16],  // 0
        [0, 0, 0.36, 0.29, 0, 0.32, 0, 0.19],  // 1
        [0.26, 0.36, 0, 0.17, 0, 0, 0.40, 0.34],  // 2
        [0, 0.29, 0.17, 0, 0, 0, 0.52, 0],  // 3
        [0.38, 0, 0, 0, 0, 0.35, 0.93, 0.37],  // 4
        [0, 0.32, 0, 0, 0.35, 0, 0, 0.28],  // 5
        [0.58, 0, 0.40, 0.52, 0.93, 0, 0, 0],  // 6
        [0.16, 0.19, 0.34, 0, 0.37, 0.28, 0, 0]   // 7
    ];

    new PrimMST(matrix)


</script>
</body>
</html>