js实现prim
Prim算法实现（JavaScript）
Prim算法是一种用于求解加权无向图最小生成树的贪心算法。以下为JavaScript实现示例：
class Graph {
constructor(vertices) {
this.V = vertices;
this.graph = Array(vertices).fill().map(() => Array(vertices).fill(0));
}
addEdge(u, v, weight) {
this.graph[u][v] = weight;
this.graph[v][u] = weight;
}
minKey(key, mstSet) {
let min = Infinity, minIndex = -1;
for (let v = 0; v < this.V; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
primMST() {
const parent = new Array(this.V).fill(-1);
const key = new Array(this.V).fill(Infinity);
const mstSet = new Array(this.V).fill(false);
key[0] = 0;
parent[0] = -1;
for (let count = 0; count < this.V - 1; count++) {
const u = this.minKey(key, mstSet);
mstSet[u] = true;
for (let v = 0; v < this.V; v++) {
if (this.graph[u][v] && !mstSet[v] && this.graph[u][v] < key[v]) {
parent[v] = u;
key[v] = this.graph[u][v];
}
}
}
this.printMST(parent);
}
printMST(parent) {
console.log("Edge \tWeight");
for (let i = 1; i < this.V; i++) {
console.log(`${parent[i]} - ${i} \t${this.graph[i][parent[i]]}`);
}
}
}
// 使用示例
const g = new Graph(5);
g.addEdge(0, 1, 2);
g.addEdge(0, 3, 6);
g.addEdge(1, 2, 3);
g.addEdge(1, 3, 8);
g.addEdge(1, 4, 5);
g.addEdge(2, 4, 7);
g.addEdge(3, 4, 9);
g.primMST();算法核心逻辑
-
初始化：创建key数组存储顶点权重，mstSet数组记录顶点是否包含在MST中，parent数组存储MST结构。
-
选择起始点：将第一个顶点作为起始点，设置key值为0。
-
循环处理：每次从未处理的顶点中选择key值最小的顶点加入MST集合。
-
更新相邻顶点：对于新加入顶点的所有相邻顶点，更新其key值和父节点。
-
输出结果：最终parent数组记录了最小生成树的边关系。
时间复杂度分析
该实现使用邻接矩阵表示图，时间复杂度为O(V²)。对于稀疏图，可以使用优先队列优化至O(E log V)。
优化建议
- 使用邻接表替代邻接矩阵存储稀疏图
- 实现优先队列（最小堆）来优化minKey操作
- 添加输入验证和错误处理机制
- 支持从文件或用户输入读取图数据
示例输出
对于上述测试图，输出结果将显示最小生成树的边及其权重：
Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5该输出表示最小生成树总权重为2+3+6+5=16。
