Prim's Algorithm for Finding a MST in a Graph
Notes
- Discovered by Robert Prim in 1957
- But apparently discoverd in 1930 by Vojtéch Jarník in 1939 (Sorry Mr. Jarník, I don't know how to make the e in your name)
- So it is sometimes called Prim-Jarník)
- This is a greedy algorithm.
- Start by selecting a random node, this will be the "root" of the tree, but don't worry that is not important.
- We will proceed by selecting the cheapest edge from this node.
- This will give us a subgraph, and we will select the cheapest edge from this subgraph
- Continue until we have added all verticies.
- Some Graphs. (These are not accessible, I will work on that).
- Two versions of Prim's
- Roughgarden
PRIM(G={V,E}) s is a random vertex, or possibly a pre-selected vertex.- X = {s}
- T = ∅
- While there is an edge (v,w) where v ∈ X and w∉ X
- Select (a,b) the minimum cost edge for which the above is true
- Add b to X
- Add (a,b) to T
- Return T
- CLRS
- While CLRS is somewhat less clear, we want their notation later
-
MST-PRIM(G,w,r) G = {V,E} w is the weight function r is the starting point- for each u ∈ G.V
- u.key = ∞
- u.π = NIL
- r.key = 0
- Q = G.V
- while Q ≠ ∅
- u = Q.Extract_Min();
- for each v ∈ G.Adjacent(u)
- if v ∈ G and w(u,v) < v.key
- v.π = u
- v.key = w(u,v)
- Roughgarden
- As the CLRS implementation implies, we should consider using a heap for the implementatino
- Let's look at CLRS's algorithm
- Line 1-3 is clearly O(|V|)
- Line 6 builds the heap, O(|V| log2|V|)
- Line 6 is O(|V|):
- All the verticies are initally in Q
- Each time in line 7 we will extract one
- Line 7 is O(log2|V|)
- So the combination is O(|V| log2|V|)
- But line 8 is tough
- In the end, we will look at each edge twice
- So this contributes a O(e)
- But line 11 is even worse.
- Since this adjusts the key for vertex v, it is O(log2|V|)
- So lines 8-11 are O(e log2|V|)
- In the end this is O(|Eog2|V| + |V| log2|V|)
- Since we expect |E| ≥ |V|, we normally say this algorithm is O(|E| log2|V|)
- CLRS notes that we can use a data structure called a Fivonacci heap.
- This changes the cost of line 11 to be O(1)
- And thus the algorithm can be implemented in O(|E| + |V| log2|V|)