Prim's algorithm

The algorithm of Prim is used to calculate a minimum spanning tree in a connected, undirected, edge-weighted graph.

The algorithm was developed in 1930 by the Czech mathematician Vojtěch Jarník. In 1957 he was first rediscovered by Robert C. Prim, Edsger W. Dijkstra 1959. Therefore, the algorithm in the literature is also sometimes performed by other names, such as Prim - Dijkstra algorithm or algorithm Jarnik, Prim and Dijkstra, in the English language algorithm also Jarnik 's or DJP algorithm.

Algorithm

The algorithm begins with a trivial graphs T, which is made from any given node of the graph. In each step, an edge is used to find a minimum weight that connects another node with T. These and the corresponding nodes are added to T. The whole is repeated until all nodes are present in T; then T is a minimum spanning tree:

• Pick any node as the starting graph T.
• As long as T is not all nodes contains: Choose an edge e of minimum weight that connects a node not contained in T v T.
• Joining e and v the graph T added.

The algorithm outlined is described by the following pseudocode:

G: graph VG: node set of G w: weight function for edge length r: start node ( r ∈ VG) Q: priority queue π [ u]: parent node of node u in the spanning tree Adj [ u]: adjacency list of u ( all neighboring nodes) worth [ u]: distance from u to the resulting spanning tree algorithmus_von_prim ( G, w, r) 01 Q VG / / Initialization 02 for all u ∈ Q 03 worth [ u] ∞ 04 π [ u] 0 05 worth [r ] 0 06 while Q ≠ 07 extract_min u (Q ) 08 for all v ∈ Adj [ u] 09 if v ∈ Q and w ( u, v) < value [v ] 10 then π [v ] u 11 value [v ] f (u, v) After the algorithm terminates, the minimum spanning tree is given as follows:

Example

In this example, the execution of the algorithm of a simple primary graph is shown. The intermediate tree is highlighted each green. All nodes that can be connected in each step via a single edge with the graph are highlighted in blue together with the respective edge of lowest weight. The node and the edge to be added are highlighted in light blue.

Comparison with the algorithm of Kruskal

Like the algorithm of Kruskal, who also constructs a minimum spanning tree, Prim algorithm is a greedy algorithm. Both algorithms start with a graph without edges and add in each step an edge with minimal weight added. They differ primarily in how the formation of a circle is avoided.

While Kruskal's algorithm globally for possible best (ie easiest ) looking edges and in the reception of these edges in the Lösungssubgraph the circle formation actively avoids the algorithm of Prim considered only edges from the nodes of the previously constructed part of nodes to nodes of the Complementary Sets proceed. Because of this (local) edge set of an edge is selected, the algorithm avoids by construction the appearance of circles.

A comparison of two algorithms based on the complexity is difficult, since the central node determining the complexity in the algorithm of barrier primary while Kruskal algorithm operates based on a sorted list of edges and, therefore, the duration of which is dominated by the number of edges.

Efficient Implementation

For an efficient implementation of the algorithm of Prim you just have to find an edge as possible, you can add the resulting tree T. So you need a priority queue ( priority queue ) in which all nodes are stored that do not yet belong to T. All nodes have a value that corresponds to the lightest edge through which the node can be connected with T. If there is no such edge, the node is assigned the value. The queue now always returns a node with the smallest value.

The efficiency of the algorithm will depend, consequently, on the implementation of the queue. When using a Fibonacci heap, an optimal term of.