Traversing through an adjacency matrix for Prim's MST algorithm

Question

I have a problem with traversing through a weighted adjacency matrix with Java. What I'm trying to do is get the weight of the minimum spanning tree from the matrix, using Prim's algorithm.

The code I have so far is the following:

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;
}

I know how traversing through the matrix is supposed to work on paper, but I'm having a problem with the implementation. More specifically, since I need to update checkThese while iterating through the list, I understand that I need to use an iterator for it, like I've tried doing. However, now the problem is that I can't figure out a way to get the r coordinate for the matrix, which I need later on. The method is missing a couple of other things too, but my main concern is how I can traverse through the matrix while updating the list of matrix rows I'm checking.

My adjacency matrix is in the form of

    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

The plan is to start with row A and choose the smallest edge (2). After that I would exclude column C from consideration, and next check rows A and C and so forth until I've excluded all columns, thus checking all the edges.

Answer 1

You need another nested loop to get it to work the way that you've indicated. Here's the corrected pseudocode.

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

This is not an especially efficient realization of Prim's algorithm. To speed it up from O(n^3) to O(n^2), the asymptotic optimum for dense matrices, you can maintain another n-element array of integers, call it minCost. The entry at index w is the minimum cost of an edge from a checked vertex to w. The revised pseudocode looks like this.

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

If all of the edge costs are positive, then you can replace the test checked[w] with minCost[w] > 0 and do away with the checked array. You also could fuse the two loops.