遍历邻接矩阵用于Prim最小生成树算法

Question

遍历邻接矩阵用于Prim最小生成树算法

javaalgorithmminimum-spanning-treeadjacency-matrix

3

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

- user1290164

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

你需要再嵌套一个循环才能按照你指示的方式使它工作。以下是已更正的伪代码。

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 数组。您还可以合并两个循环。