mincel.com - Prim's Algorithm

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted 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. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components. The algorithm was discovered in 1930 by mathematician Vojtech Jarnik and later independently by computer scientist Robert Prim in 1957 and rediscovered by Dijkstra in 1959. Therefore it is sometimes called DJP algorithm or Jarnik algorithm.

It works as follows:

create a tree containing a single vertex, chosen arbitrarily from the graph
create a set containing all the edges in the graph
loop until every edge in the set connects two vertices in the tree
- remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
- add that edge to the tree

Using a simple binary heap data structure, Prim's algorithm can be shown to run in time which is O((m + n) log n) where m is the number of edges and n is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(m + nlog n), which is significantly faster when the graph is dense enough that m is ω(nlog n).

Prim's Algorithm (Java Applet)

1. Select Add Node, click on the drawing canvas to add nodes. The Locate button adds nodes automatically.
2. Select Add Edge, give an edge weight and select two nodes to add an edge.
If the given edge weight is bigger than 99 it will be set to 99. If an edge weight in not given it will be a random number between 1 and 99.
3. To change an edge weight, select Change, select an edge and change the edge weight.

Download the source code.