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.
Example run
| Image | U | possible edges | V \ U | Description |
|---|---|---|---|---|
 | {} | {A,B,C,D,E,F,G} | This is our original weighted graph. The numbers near the edges indicate their weight. | |
 | {D} | {D,A} = 5 V {D,B} = 9 {D,E} = 15 {D,F} = 6 | {A,B,C,E,F,G} | Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD. |
 | {A,D} | {D,B} = 9 {D,E} = 15 {D,F} = 6 V {A,B} = 7 | {B,C,E,F,G} | The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the edge DF. |
 | {A,D,F} | {D,B} = 9 {D,E} = 15 {A,B} = 7 V {F,E} = 8 {F,G} = 11 | {B,C,E,G} | The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted. |
 | {A,B,D,F} | {B,C} = 8 {B,E} = 7 V {D,B} = 9 cycle {D,E} = 15 {F,E} = 8 {F,G} = 11 | {C,E,G} | In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away fromB, and G is 11 away from F. E is nearest, so we highlight the vertex E and the edge BE. |
 | {A,B,D,E,F} | {B,C} = 8 {D,B} = 9 cycle {D,E} = 15 cycle {E,C} = 5 V {E,G} = 9 {F,E} = 8 cycle {F,G} = 11 | {C,G} | Here, the only vertices available are C and G.C is 5 away from E, and G is 9 away from E.C is chosen, so it is highlighted along with the edge EC. |
 | {A,B,C,D,E,F} | {B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {E,G} = 9 V {F,E} = 8 cycle {F,G} = 11 | {G} | Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight G and the edge EG. |
 | {A,B,C,D,E,F,G} | {B,C} = 8 cycle {D,B} = 9 cycle {D,E} = 15 cycle {F,E} = 8 cycle {F,G} = 11 cycle | {} | Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39. |
Implementation:
import java.io.*;
class Tnode
{
int prev;
int len;
char label;
boolean vis;
public Tnode(char lab)
{
label = lab;
prev=-1;
len=100000;
vis=false;
}
}
