Skip to content

Instantly share code, notes, and snippets.

@soundsmitten
Created December 12, 2012 22:39
Show Gist options
  • Select an option

  • Save soundsmitten/4272320 to your computer and use it in GitHub Desktop.

Select an option

Save soundsmitten/4272320 to your computer and use it in GitHub Desktop.
Java- Prim's minimum spanning tree
// From Wikipedia: Prim's algorithm is a greedy algorithm that
// finds a minimum spanning tree for a connected weighted undirected graph.
// This means it finds a subset of the edges that forms a tree that
// includes every vertex, where the total weight of all the edges in the tree is minimized.
void Prim(int n, int[][] W, int[] nearest)
{
int[]distance
for( i = 1; i<=n; i++)
{
nearest[i] = 1
distance[i] = W[1][i]
}
for (j=1; j<=n-1; j++) {
min = distance[1] // or min = infinity
vnear = n-1 // or min = infinity
for (i=1; i<=n; i++) {
if (distance[i] < min && distance[i] > 0) {
min = distance[i];
vnear = i;
}
}
distance [vnear] = 0;
for (i= 1; i<=n; i++) {
if (W[vnear][i] < distance[i]) {
distance[i] = W[vnear][i]
nearest[i] = vnear;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment