普里姆算法 [英] Prim's Algorithm
问题描述
我正在使用带有Java中PriorityQueue的 Prim算法来研究最小生成树.但是,我弄错了totalWeight(树的最小权重).
I am working on a minimum spanning tree using Prim's Algorithm with PriorityQueue in Java. However, I am getting the totalWeight (the minimum weight of the tree) wrong.
我是否误解了总重量的概念,还是我的代码有问题?
Did I misunderstand the concept behind total weight, or is there some problem with my code?
public int getMinSpanningTree(Graph g) {
int[][] matrix = g.getEdgeMatrix();
int totalVertices = g.getNumberOfVertices();
boolean[] visit = new boolean[totalVertices];
int visitNum = 1;
int totalWeight = 0;
PriorityQueue<PriorityVertex> queue = new PriorityQueue<PriorityVertex>();
//FIRST ITERATION
visit[0] = true;
for (int i = 0; i < totalVertices; i++) {
if(matrix[0][i] > 0) {
PriorityVertex temp = new PriorityVertex(i, g.getWeight(0,i));
queue.add(temp);
}
}
while (visitNum < totalVertices) {
PriorityVertex temp = queue.poll();
visit[temp.vertex] = true;
visitNum++;
totalWeight = temp.priority + totalWeight;
//RUN NEIGHBOUR VERTICES
for (int k = 0; k < totalVertices; k++) {
if(matrix[temp.vertex][k] > 0 && visit[k] == false) {
PriorityVertex vertex = new PriorityVertex(k, g.getWeight(temp.vertex, k));
queue.add(vertex);
}
}
}
return totalWeight;
}
推荐答案
问题是您没有从队列中删除所有顶点实例=>同一顶点可以多次添加到结果中.
The problem is you do not remove all instances of vertex from the queue => the same vertex can be added several times into the result.
假设下图:
weight(0,1) = 1
weight(0,2) = 2
weight(1,2) = 3
weight(1,3) = 4
weight(2,3) = 5
在"FIRST ITERATION"之后,队列包含PriorityVertex(1,1),PriortyVertex(2,2).
After the "FIRST ITERATION" the queue contains PriorityVertex(1, 1), PriortyVertex(2, 2).
while循环的迭代次数:
Iterations of while cycle:
1) removed: PriorityVertex(1, 1) - edge (0,1)
added: PriorityVerterx(2, 3) and PriorityVertex(3, 4)
queue: PriorityVertex(2, 2), PriorityVertex(2, 3), PriorityVertex(3, 4)
2) removed: PriorityVertex(2, 2) - edge (0,2)
added: PriorityVertex(3, 5)
queue: PriorityVertex(2, 3), PriorityVertex(3, 4), PriorityVertex(3, 5)
3) removed: PriorityVertex(2, 3) - edge (1,2), cycle in the result!
这篇关于普里姆算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!