The greed technique solves an optimization problem by iteratively building a solution. It always selects the optimal solution each iteration. Because the problem is an optimization, greedy algorithms use a priority queue.
Consider the making change returning the minimal number of coins. Almost everyone uses a greedy approach, first returning the largest domination coin that does not exceed the amount left to return. What items does the priority queue contain?
The greedy technique works for our denominations of coins, meaning quarters, dimes, nickels and pennies. It does not always work, consider the denominations of that included 7c, 5c and 1c. Make change on 10c using the greedy technique.
Prim's Algorithm constructs a
minimal spanning tree (MST) in a connect graph or component.
A minimal spanning tree of a weighted graph is a spanning tree that has minimal of sum of edge weights.
Prim's Algorithm solves the greedy algorithm using the greedy technique. It builds the spanning tree by adding the minimal weight edge to a vertex not already in the tree.
Algorthm Prim(G)
VT ← {v0}
ET ← {} // empty set
for i ← 1 to |V| do
find the
minimum weight edge, e* = (v*, u*)
such that v* is in VT and u is in
VT ← VT union {u*}
ET ← ET union {e*}
return ET
Illustrate the algorithm
Typically the greedy algorithms are easy to write. Proving that they construct the optimal solution can be difficult.
We prove Prim's algorithm is correct by induction on the growing tree constructed by the algorithm. We assume that Ti-1 is part of a minimal spanning tree for the graph and prove that the tree Ti constructed using Prim's algorithm must be part of a minimal spanning tree. Then Tn is a minimal spanning tree for the complete graph.
T0 is a single vertex so it must be part of a minimal spanning tree.
We assume that Ti-1 is part of a minimal spanning tree. Let T be the minimal spanning tree such that Ti-1 is part of T. We prove by contraction that Ti is part of a minimal spanning tree.
Let ei = (v, u) be the edge found by Prim's algorithm and assume that it is not an edge of a minimum spanning tree. Then ei cannot be part of T.
Recall that Ti-1 is a spanning tree of the vertices of Ti-1 and is also part of T, a spanning tree of the complete graph, so there must be an edge (v', u') in T that connects the vertices of Ti-1 to a vertex not in Ti-1. Note that ei also connects vertices in Ti-1 with vertices not in Ti-1 therefore the Graph T + ei has a cycle with edges (v', u') and ei part of the cycle. If we delete the edge (v', u') from T + ei, the remaining graph, T + ei - (v', u'), is another spanning tree. Because (v', u') and ei are both edges with origins in vertices Ti-1 and also ei is edge from Prim's algorthim the weight of ei must be less than or equal to the weight of (v', u'). So the total weight of T + ei - (v', u') is less than or equal to T. Therefore T + ei - (v', u') is a minimal spanning tree of the complete graph with the edge ei. This is a contradiction that ei was not part of minimal spanning tree. So, Prim's algorithm constructs a minimal spanning tree.
Below is another version of Prim's algorithm with explicit priority queue.
Algorthm Prim(G)
VT ← {v0}
ET ← {} // empty set
make
Priority Queue of vertices, Q, // is
the V-VT
initialize with weights of the minimal edge adjacent to v0
if the vertex is not adjacent to v0 then the weight is ∞
for i ← 1 to |V| do
u* ← remove minimum from Q // the optimal choice in V-VT
for each u adjacent to u* in Q do
update u in Q with min(current key of u, w(u*, u))
VT ← VT union {u*}
ET ← ET union {e*}
return ET
Consider that Q is implemented with a heap. What is the cost of updating u in Q? lg | Q | ε O(lg n), why? We assume that vertices are aware of their location in Q, but then it location must be update using bubble up or down.
How many update are performed?
The for-loop ovre adjacent vertices runs the degree of u*. So for the complete algorithm
∑v ε V degree(v) = 2m (2 times the number of edges). Why? because all edges are counted trice in the sum.
Remember this formula
The total cost of the algorithm in worst case includes constructing the priority queue.
O(n lg n + m lg n) = O((n+m)lg n)
Were the n lg n is cost of initializing Q.
If the graph is connected then n ε O(m), so the algorithm is O(m lg n)