Skip to content

Commit e5b0d33

Browse files
taokexiataokexia
committed
add prim
1 parent 3d3f313 commit e5b0d33

4 files changed

Lines changed: 128 additions & 2 deletions

File tree

‎JavaScript/RightGraph/Edge.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,7 @@ module.exports = class Edge {
2626
}
2727
// 输出边的信息
2828
toString() {
29-
let str = ""+this.a+"-"+this.b+":"+this.weight;
29+
let str = ""+this.a+"-"+this.b+":"+this.weight+"\n";
3030
return str;
3131
}
3232
}

‎JavaScript/RightGraph/LazyPrimMST.js‎

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
var MinHeap = require('./MinHeap');
2+
var Edge = require('./Edge');
3+
// 使用Prim算法求图的最小生成树
4+
module.exports = class LazyPrimMST {
5+
constructor(g) {
6+
this.data = g.g; // 传入的图类的数据
7+
this.pq = new MinHeap(); // 最小堆，算法辅助数据结构
8+
this.marked = new Array(g.V()).fill(false); // 标记数组，在算法运行过程中记录节点i是否被访问过
9+
this.mst = []; // 用于记录最小生成树所包含的边
10+
this.mstWeight; // 最小生成树的权值
11+
12+
// Lazy Prim
13+
this.visit(0);
14+
while(!this.pq.isEmpty()) {
15+
// 使用最小堆找出已经访问过的边中权值最小的边
16+
let e = this.pq.extractMin();
17+
// console.log(this.pq);
18+
// 如果这条边的两端都已经被访问过，则扔掉这条边
19+
if(this.marked[e.v()] === true && this.marked[e.w()] === true)
20+
continue;
21+
// 否则，这条边应该存在在最小生成树中
22+
this.mst.push(e);
23+
// 访问和这条边连接的还没被访问过的节点
24+
if(!this.marked[e.v()]) {
25+
this.visit(e.v());
26+
} else {
27+
this.visit(e.w());
28+
}
29+
}
30+
31+
// 计算最小生成树的权值
32+
this.mstWeight = this.mst[0].wt();
33+
for(let i = 1; i < this.mst.length; i++) {
34+
this.mstWeight += this.mst[i].wt();
35+
}
36+
}
37+
// 访问节点
38+
visit(v) {
39+
if(this.marked[v]) return;
40+
this.marked[v] = true;
41+
// 将和节点v相连的所有为访问节点的边放入最小堆中
42+
for(let i = 0; i < this.data[v].length; i++) {
43+
let e = this.data[v][i];
44+
if(!this.marked[e.other(v)])
45+
this.pq.insert(e);
46+
}
47+
}
48+
// 返回最小生成树的所有边
49+
mstEdges() {
50+
return this.mst;
51+
}
52+
// 返回最小生成树的权值
53+
result() {
54+
return this.mstWeight;
55+
}
56+
}

‎JavaScript/RightGraph/MinHeap.js‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
/*
2+
* 最小堆
3+
*/
4+
module.exports = class MinHeap {
5+
constructor() {
6+
this.data = [];
7+
this.count = 0;
8+
}
9+
init(arr) {
10+
this.data = arr;
11+
this.count = arr.length;
12+
for(let i = Math.floor(this.count/2)-1; i >= 0; i--) {
13+
this.shiftDown(i);
14+
}
15+
}
16+
shiftUp(k) {
17+
while(k > 0 && this.data[Math.floor((k-1)/2)].wt() > this.data[k].wt()) {
18+
this.swap(Math.floor((k-1)/2), k);
19+
k = Math.floor((k-1)/2);
20+
}
21+
}
22+
shiftDown(k) {
23+
while(2*k+1 < this.count) {
24+
let j = 2*k+1;
25+
if(j+1 < this.count && this.data[j+1].wt() < this.data[j].wt()) j++;
26+
if(this.data[k].wt() <= this.data[j].wt()) break;
27+
this.swap(k, j);
28+
k = j;
29+
}
30+
}
31+
insert(edge) {
32+
this.data[this.count] = edge;
33+
this.shiftUp(this.count);
34+
this.count++;
35+
}
36+
extractMin() {
37+
if(this.count <= 0) return;
38+
let value = this.data[0];
39+
this.swap(0, this.count-1);
40+
this.count--;
41+
this.shiftDown(0);
42+
return value;
43+
}
44+
getMin() {
45+
if(this.count <= 0) return;
46+
return this.data[0];
47+
}
48+
size() {
49+
return this.count;
50+
}
51+
isEmpty() {
52+
return this.count === 0;
53+
}
54+
swap(a, b) {
55+
let t = this.data[a];
56+
this.data[a] = this.data[b];
57+
this.data[b] = t;
58+
}
59+
}

‎JavaScript/RightGraph/Test.js‎

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,4 +38,15 @@ sg.addEdge(6, 2, 0.40);
3838
sg.addEdge(3, 6, 0.52);
3939
sg.addEdge(6, 0, 0.58);
4040
sg.addEdge(6, 4, 0.93);
41-
sg.show();
41+
sg.show();
42+
43+
console.log("======================================测试最小生成树====================================");
44+
var LazyPrimMST = require('./LazyPrimMST');
45+
var lpm = new LazyPrimMST(sg);
46+
var mst = lpm.mstEdges();
47+
var str = "";
48+
for(let i = 0; i < mst.length; i++) {
49+
str += mst[i].toString();
50+
}
51+
console.log(str);
52+
console.log("The MST weight is "+ lpm.result());

0 commit comments

Comments
 (0)