带优化的 prim
从上文求出的最小生成树，可以发现有很多重复的选项被判断，而且最小堆里面存在很多相同的顶点不同边，没有及时判断出那条边是最小的情况，理应得到当前顶点相连的最小的边，其他的排除掉，减少执行的判断，减少复杂度。
代码实现
const IndexReverseMinHeap = require('./index-reverse-min-heap');
class PrimMST {
constructor(g) {
this.g = g; // 图的引用
const compare = (parent, child) => {
return parent && child && parent.weight > child.weight;
};
this.ipq = new IndexReverseMinHeap(compare); // 最小索引堆模拟优先队列
this.edgeTo = new Array(g.V()).fill(null); // 访问的点对应的边
this.marked = new Array(g.V()).fill(false); // 标记数组，标记节点是否被访问过
this.mst = []; // 最小生成树包含的边
this.mstWeight = 0; // 最小生成树的权值
// prim
this.visit(0);
while (!this.ipq.isEmpty()) {
// 使用最小索引堆找出已经访问的边中权值最小的边
// 最小索引堆中存储的是点的索引，通过点的索引找到对应的边
const v = this.ipq.extractMinIndex();
this.mst.push(this.edgeTo[v]);
this.visit(v);
}
for (const e of this.mst) {
this.mstWeight += e.wt();
}
}
visit(v) {
if (this.marked[v]) return;
this.marked[v] = true;
for (const e of this.g.adj(v)) {
const w = e.other(v);
// 边的另一个端点没有被访问
if (!this.marked[w]) {
// 如果没有考虑过这个端点，直接将这个端点和与之相连的边加入索引堆
if (!this.edgeTo[w]) {
this.edgeTo[w] = e;
this.ipq.insert(w, e.wt());
} else if (e.wt() < this.edgeTo[w].wt()) {
// 考虑过这个端点，但是现在这条边比之前考虑的更短，则进行替换
this.edgeTo[w] = e;
this.ipq.change(w, e.wt());
}
}
}
}
mstEdges() {
return this.mst;
}
result() {
return this.mstWeight;
}
}
module.exports = PrimMST;