我在使用 Java 遍历加权邻接矩阵时遇到问题。我要做的是使用 Prim 算法从矩阵中获取最小生成树的权重。
我目前的代码如下:
public int findPrim(int[][] matrix) {
ArrayList < Integer > checkThese = new ArrayList < > ();
checkThese.add(0); //Starting vertex.
boolean[] checked = new boolean[graph.vertexCount()];
int w = 0;
int column = 0;
int row = 0;
int smallest = 0;
for (Iterator < Integer > it = checkThese.Iterator(); it.hasNext();) {
smallest = Integer.MAX_VALUE;
for (int k = 0; k < graph.vertexCount(); k++) {
if ((matrix[r][k] < smallest) && matrix[r][k] != 0 && !checked[k - 1]) {
smallest = matrix[r][k];
column = k;
}
}
if (smallest != Integer.MAX_VALUE) {
w += smallest;
checkThese.add(column);
checked[column] = true;
}
}
return w;
}
我知道在纸面上应该如何遍历矩阵,但我在实现时遇到了问题。更具体地说,由于我需要在遍历列表时更新 checkThese
,我知道我需要为其使用迭代器,就像我尝试过的那样。但是,现在的问题是我想不出一种方法来获取矩阵的 r
坐标,我稍后需要它。该方法还缺少其他一些东西,但我主要关心的是如何在更新我正在检查的矩阵行列表的同时遍历矩阵。
我的邻接矩阵是
A B C D E
A 0 4 2 8 0
B 0 0 5 6 7
C 0 0 0 9 3
D 0 0 0 0 1
E 0 0 0 0 0
计划是从 A
行开始并选择最小的边 (2)。之后我会排除 C
列的考虑,接下来检查行 A
和 C
等等,直到我排除所有列,因此检查所有边。
最佳答案
您需要另一个嵌套循环才能使其按照您指定的方式工作。这是更正后的伪代码。
let n be the number of vertices
initialize cost <- 0
initialize checkThese <- [0]
initialize checked <- [true, false, ..., false] (length n)
repeat n - 1 times (alternatively, test for termination as indicated)
smallest <- infinity
argSmallest <- null
for v in checkThese
for w from 0 to n - 1
let cost = matrix[min(v, w)][max(v, w)]
if not checked[w] and cost < smallest then
smallest <- cost
argSmallest <- w
end if
end for
end for
(break here if argSmallest is null)
cost <- cost + smallest
add argSmallest to checkThese
checked[argSmallest] <- true
end repeat
这不是 Prim 算法的特别有效的实现。为了将它从 O(n^3) 加速到 O(n^2),即密集矩阵的渐近最优,您可以维护另一个 n 元素整数数组,将其称为 minCost
。索引 w
处的条目是从已检查顶点到 w
的边的最小成本。修改后的伪代码如下所示。
let n be the number of vertices
initialize cost <- 0
initialize checked <- [true, false, ..., false] (length n)
initialize minCost <- [0, infinity, ..., infinity] (length n)
repeat n - 1 times (alternatively, test for termination as indicated)
smallest <- infinity
argSmallest <- null
for w from 0 to n - 1
if not checked[w] and minCost[w] < smallest then
smallest <- minCost[w]
argSmallest <- w
end if
end for
(break here if argSmallest is null)
cost <- cost + smallest
checked[argSmallest] <- true
minCost[argSmallest] <- 0
for v from 0 to n - 1
let cost = matrix[min(argSmallest, v)][max(argSmallest, v)]
if not checked[v] and cost < minCost[v] then
minCost[v] <- cost
end if
end for
end repeat
如果所有边成本都是正数,那么您可以将测试 checked[w]
替换为 minCost[w] > 0
并取消 checked
数组。您也可以融合这两个循环。
关于java - 遍历 Prim 的 MST 算法的邻接矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22746421/