Mathematical
Programming
 		Prim's Algorithm

Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson

Prim
JavaScript 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.
  1. Set i=0, S0= {u0=s}, L(u0)=0, and L(v)=infinity for v <> u0. If |V| = 1 then stop, otherwise go to step 2.
  2. For each v in V\Si, replace L(v) by min{L(v), dvui}. If L(v) is replaced, put a label (L(v), ui) on v.
  3. Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
  4. Let Si+1 = Si cup {ui+1}.
  5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.
The time required by Prim's algorithm is O(|V|2). It will be reduced to O(|E|log|V|) if heap is used to keep {v in V\Si : L(v) < infinity}.

Java Source File:

JavaScript Demos

See Also

Kenji Ikeda's
Home Page		 Last Modified: Tuesday, 01-Sep-2015 14:05:32 JST