Simplex
Twophase
Dijkstra
Prim
Kruskal
FordFulkerson
Prim Java applet demos:
FAQ
Japanese/English

MST Problem
Given a connected graph G=(V,E) and a weight d:E>R+,
find a minimum spanning tree.
Prim's Algorithm
Prim's algorithm is known to be a good algorithm to find
a minimum spanning tree.
 Set i=0, S_{0}= {u_{0}=s},
L(u_{0})=0, and L(v)=infinity for v <> u_{0}.
If V = 1 then stop, otherwise go to step 2.
 For each v in V\S_{i}, replace L(v) by
min{L(v), d_{v}^{ui}}.
If L(v) is replaced, put a label (L(v), u_{i}) on v.
 Find a vertex v which minimizes {L(v): v in V\S_{i}},
say u_{i+1}.
 Let S_{i+1} = S_{i} cup {u_{i+1}}.
 Replace i by i+1. If i=V1 then stop, otherwise go to step 2.
The time required by Prim's algorithm is O(V^{2}).
It will be reduced to O(ElogV)
if heap is used to keep {v in V\S_{i} : L(v) < infinity}.
Java Source File:
Java Applet Demos
See Also
