-
Notifications
You must be signed in to change notification settings - Fork 10
/
LazyPrim.html
85 lines (80 loc) · 2.46 KB
/
LazyPrim.html
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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Prim</title>
</head>
<body>
<script src="../Graph%20Theory/Edge.js"></script>
<script>
// 最小生成树 - prim算法 - 切分定理
class lazyPrim {
constructor(matrix) {
this.rows = matrix.length;
this.marked = [];
this.matrix = [];
this.pq = [];
this.mst = [];
for (let i = 0; i < this.rows; i++) {
this.marked[i] = false
}
//初始化矩阵
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]))
}
}
}
}
visit(v) {
if (this.marked[v]) return;
this.marked[v] = true;
let e;
for (let i = 0; i < this.matrix[v].length; i++) {
e = this.matrix[v][i];
if (!this.marked[e.other(v)]) {
this.pq.push(e)
}
}
}
buildMST() {
this.visit(0);
while (this.pq.length) {
this.pq = this.pq.sort((a, b) => {
return a.weight - b.weight
});
let minVet = this.pq.shift();
if (this.marked[minVet.v()] === this.marked[minVet.w()]) {
continue;
}
this.mst.push(minVet);
if (!this.marked[minVet.v()]) {
this.visit(minVet.v())
} else {
this.visit(minVet.w())
}
}
}
}
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 lazyPrim(matrix)
</script>
</body>
</html>