Prim

Algorithmic problem: Minimum spanning tree

Prerequisites:

Type of algorithm: loop

Auxiliary data:

1. A key for each node .
2. A priority queue of nodes. The key of a node for is , the information is one of the edges of that is incident to .

Abstract view

Invariant: After iterations:

1. There is a node set of size and an edge set such that solely connects nodes in , and is a tree.
2. There is a minimum spanning tree of such that .
3. The key of is the minimal length of an edge that connects with some node in (or , if there is no such edge). If and , this edge is the information associated with in .

Note that, once a node joins , its key will be irrelevant for the rest of the algorithm. Variant: increases by . Break condition:  ; then return .

Induction basis

Abstract view:

1. Choose an arbitrary node and set .
2. For each node :
   1. If , set , otherwise set .
   2. Insert with key in .

Implementation: Obvious. Proof: Obvious.

Induction step

Abstract view:

1. Extract the first node from .
2. Let denote the edge stored as information for in .
3. For each such that and :
   1. Set as the new information for in .
   2. Set .
   3. Rearrange according to the decreased key .
4. .
5. .

Implementation: Obvious. Correctness: The first and third invariants are obviously maintained, so we will focus on the second invariant. Let denote the other endnode of , so it is . Since is a spanning tree of , there is exactly one path in connecting and . As is cycle-free and contains the tree , contains exactly one edge such that and . If (and thus ), the invariant is maintained by . So consider the case that . Note that immediately before the -th iteration. Therefore, the specific choice of implies . So, with we obtain a spanning tree of whose weight is not larger than that of , which is minimum by definition.

Complexity

Statement: in the worst case, where and and is the asymptotic complexity of the methods of .

Proof: In the preprocessing, nodes are to be inserted in , which takes time. Since each node is inserted at most once, all extraction operations take time, too. For each edge, has to be rearranged at most once, which results in time. Clearly, all other operations of the preprocessing and the main loop are dominated by these bounds as well.