Prim
General information
Algorithmic problem: Minimum spanning tree
Prerequisites:
Type of algorithm: loop
Auxiliary data:
- A key
for each node . - 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
- There is a node set
of size and an edge set such that solely connects nodes in , and is a tree. - There is a minimum spanning tree
of such that . - 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
Variant:
Break condition:
Induction basis
Abstract view:
- Choose an arbitrary node
and set . - For each node
:- If
, set , otherwise set . - Insert
with key in .
- If
Implementation: Obvious.
Proof: Obvious.
Induction step
Abstract view:
- Extract the first node
from . - Let
denote the edge stored as information for in . - For each
such that and :- Set
as the new information for in . - Set
. - Rearrange
according to the decreased key .
- Set
. .
Implementation: Obvious.
Correctness: The first and third invariants are obviously maintained, so we will focus on the second invariant. Let
Since
Note that
Complexity
Statement:
Proof: In the preprocessing,