java - 遍历 Prim 的 MST 算法的邻接矩阵

Question

我在使用 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 等等，直到我排除所有列，因此检查所有边。

Answer 1

您需要另一个嵌套循环才能使其按照您指定的方式工作。这是更正后的伪代码。

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 数组。您也可以融合这两个循环。