Minimal Spanning Tree from adjacency matrix in Java

Question

Please, help me to understand how to get minimal spanning tree from adjacency matrix of graph! I write coursework about it in java, deadline is 16.12.2010, but I feel that it shall be fail. Now my program can:

1. Draw nodes
2. Draw edges
3. Generate adjacency matrix of graph on basement of your drawing with weight of edges
4. Find minimal edge connected to node
5. and have some other testing / tested features

But I don't know how realize Prim / Kruskal algorhythm in Java. I try to find some resolves in google, but find only Java-applet, that needs to work .obj files, also I can't run it.

I write some Simple console java pattern that now generate and print adjacency matrix of graph. Can anybody add function that returns adjacency matrix of minimal spanning tree of graph looking like:

public static int[][] mst(int[][] graph, int n) {
    ...
}

where:

• graph - is generated graph in n
• amount of vertexes (nodes)

Thanks in advance!

Answer 1

Given your program at the moment can't handle the Disjoint Set Data Structure, you'd probably want to use Prim's.

Seeing that you can already do most of the things required to do Prim's, I'll give it to you in pseudocode.

int bestDist[N]
int mst[N][N]
int cameHere[N]
bool done[N]
FOR i = 0..N-1:
 bestDist[i] = INFINITY
 done[i] = false
 FOR j=0..N-1:
  mst[i][j] = INFINITY

// start at any node
bestDist[0] = 0;
FOR i = 0..N-1:
 bestNode = INFINITY
 bestNodeDist = INFINITY

 IF bestNode != 0:
  mst[cameHere[bestNode]][bestNode] = graph[cameHere[bestNode]][bestNode]

 // find closest node
 FOR j= 0..N-1:
  IF !done[j] AND bestDist[j] < bestNodeDist:
   bestNode = j
   bestNodeDist = bestNodeDist[j]

 // update surrounding nodes
 FOR j=0..N-1:
  IF !done[j] AND bestNodeDist + graph[bestNode][j] < bestDist[j]:
   bestDist[j] = bestNodeDist + graph[bestNode][j]
   cameHere[j] = bestNode

return mst

This runs in O(N^2) but you can make it run in O(E log E), where E = num edges if you uses a heap.

Answer 2

If anyone is looking for MST with adjacency matrix implementation there's my sample code in Java. I post it because Junkbot answer lacks some details. It runs in O(n^2) so Prim's algorithm is the best choice for dense / full graph for finding MST.

    public void MST-Prim()
    {
    int[] source = new int[numberOfVertices]; // i-th element contains number of source vertex for the edge with the lowest cost from tree T to vertex i
    double[] dist = new double[numberOfVertices]; //i-th element contains weight of minimal edge connecting i with source[i] 
    indicators = new boolean[numberOfVertices];  //if true, vertex i is in tree T

    // Mark all vertices as NOT being in the minimum spanning tree
    for (int i = 0; i < numberOfVertices; i++)
    {
        indicators[i] = false;
        dist[i] = Double.POSITIVE_INFINITY;
    }

     //we start with vertex number 0
    indicators[0] = true;
    dist[0] = 0;
    int bestNeighbour = 0;// lastly added vertex to the tree T 
    double minDist; 

    for (int i = 0; i < numberOfVertices - 1; i++)
    {
        minDist = Double.POSITIVE_INFINITY;

        for (int j = 0; j < numberOfVertices; j++) // fill dist[] based on distance to bestNeighbour vertex
        {
            if (!indicators[j])
            {
                double weight = fullGraph.getEdgeWeight(bestNeighbour, j);

                if (weight < dist[j])
                {
                    source[j] = bestNeighbour;
                    dist[j] = weight;
                }
            }
        }

        for (int j = 0; j < numberOfVertices; j++) // find index of min in dist[]
        {
            if (!indicators[j])
            {
                if (dist[j] < minDist)
                {
                    bestNeighbour = j;
                    minDist = dist[j];
                }
            }
        }

        if (bestNeighbour != 0)
        {//add the edge (bestNeighbour, dist[bestNeighbour]) to tree T
            addEdgeToTree(new GraphEdge(fullGraph.getNode(source[bestNeighbour]), fullGraph.getNode(bestNeighbour),
                    dist[bestNeighbour]));
            indicators[bestNeighbour] = true;
        }

    }

}