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.