JavaScriptAlgorithms/Minimum Span Tree/kruskal.html at master · biaodigit/JavaScriptAlgorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>
<script src="../Graph%20Theory/Edge.js"></script>
<script>
    class kruskalMST {
        constructor(matrix) {
            this.matrix = [];
            this.pq = [];
            this.mst = [];
            this.initMatrix(matrix);
            this.uf = new UnionFind(matrix.length);

            for (let i = 0; i < this.matrix.length; i++) {
                for (let j = 0; j < this.matrix[i].length; j++) {
                    let e = this.matrix[i][j];
                    if (e.v() < e.w()) {
                        this.pq.push(e)
                    }
                }
            }
            this.pq = this.pq.sort((a, b) => {
                return a.wt() - b.wt()
            });
            this.buildMST()
        }

        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() {
            while (this.pq.length) {
                let e = this.pq.shift();
                if (this.uf.isConnected(e.v(), e.w())) continue;
                this.mst.push(e);
                this.uf.unionElements(e.v(), e.w())
            }
        }
    }

    class UnionFind {
        constructor(n) {
            this.parent = Array(n);
            this.count = n;
            this.rank = Array(n);
            for (let i = 0; i < n; i++) {
                this.parent[i] = i;
                this.rank[i] = 1;
            }
        }

        find(p) {
            if (p < 0 || p >= this.count) return;
            if (p !== this.parent[p]) {
                this.parent[p] = this.find(this.parent[p])
            }
            return this.parent[p]
        }

        isConnected(p, q) {
            return this.find(p) === this.find(q);
        }

        unionElements(p, q) {
            let pRoot = this.find(p),
                qRoot = this.find(q);
            if (pRoot === qRoot) return;
            if (this.rank[pRoot] < this.rank[qRoot]) {
                this.parent[pRoot] = qRoot;
            } else if (this.rank[pRoot] > this.rank[qRoot]) {
                this.parent[qRoot] = pRoot;
            } else {
                this.parent[pRoot] = qRoot;
                this.rank[qRoot]++;
            }
        }
    }

    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 kruskalMST(matrix)
</script>
</body>
</html>