### graph mst prim

#########################################
####   minimum spanning tree (MST)   ####
#########################################

a greedy algo that computes a minimum spanning tree for a "connected" "weighted" "undirected" graph. (can have negative path weights)

a minimum spanning tree for a graph G=(V,E) means a subset of E that connects all vertices in V, and the total weight of all edges combined is the smallest possible. (obviously the number of edges is n-1 for any spanning trees, where n = # of nodes)

a greedy algo means divide a problem into subproblems, and independently optimally resolve each in the order of some prioritization. not always guaranteed to produce the most optimal solution (in this case "minimum") for all problems, but works for prim's algo. the diff against dynamic programming is that no memoization of info on the solution of each subproblems.

(ref)
http://en.wikipedia.org/wiki/Prim's_algorithm
http://en.wikipedia.org/wiki/Greedy_algorithm   // jpn ver. is very good also
http://en.wikipedia.org/wiki/Minimum_spanning_tree

note: as for the "undirected" property, it is required because if you think about an MST, and if it is directed, it defies the very definision of MST. How does one know the path between arbitrary two vertices? This is to be contrasted to a similar logic algo like Dijkstra's where the algo can take in directed graph because it always looks at the directed from the source vertex to the rest of the vertices in the graph. of course, in this sense, undirected graph means directed graph where every edge is bidirectional.

#########################
####   prim's algo   ####
#########################

##
## logic flow:
##

similar to dijkstra's algo
(1) randomly choose a start vertex s, and put it into an initially empty set S. (while taking s out from V)
(2) then update the weight/pred info for all edges of s
(3) then take a vertex v with the smallest weight, and put it into S (out of V)
(4) then update the weight/pred info for all edges of v, except for edge(v,t) where t is already in S
(5) repeat (3)(4) until S = V

so for each v in V, you can trace pred[v] to construct a MST. note pred[s] = -1

---------------------------- // psuedo code

computeMST()

foreach v (V)   // init loop
{
w[v] = inf;
pred[v] = -1;
}
w[s] = 0;
pq = new PQ;
foreach v (V)
pq.insert(v,w[v]);  // insert v as a node, using w[v] as a key

while(!pq.empty())
{
u = pq.getMin();  // put u into S set
foreach v (immediate neighbors of u)
{
if(pq.contains(v))  // if not contained, that means that guy is already examined/connected
{
d = w(e(u,v));  //  weight of edge(u,v)
if(d < w[v])
{
pred[v] = u;
w[v] = d;
pq.decreaseKey(v,d);  // bubble up v with a new key val "d"
}
}
}
}

----------------------------

(ref)
Algorithm in a nutshell. Heineman, et al.

###
###  Dijkstra  VS  Prim
###

Interestingly, Prim's MSP algo logic looks very similar to Dijkstra's SSSP algo.
but notice, in Dijkstra, we always update the known shortest distance to un-popped V "from the source vertex s", whereas in Prim, we always update the distance "from ANY vertices already in S".

a very good example graph that shows the difference is in the ref.
(ref)
http://stackoverflow.com/questions/1909281/use-dijkstras-to-find-a-minimum-spanning-tree

##
##  complexity analysis:
##

for initialization
a for loop for setting each key[v]: O(V)
a for loop for inserting each v into PQ: O(V * log V)

for the main while loop
for each v, we look at all its edges, this means O(2E)
decreaseKey() : O(log V)
(note: as discussed in dijkstra algo article, we probably need a map of key-ops in PQ heap array)

thus in total: O(V + V*logV + 2E*logV) = O((V+E) * log V)

##
##  proof of correctness
##

(taken from the math.wikia.com)

let T' be a MST of G=(V,E)
let T be the spanning tree of G, generated by Prim's algo.
T consists of n-1 edges = {e0, e1, e2,,, ek,,, en} where ek being the edge chosen at the kth iteration.

we want to prove T = T'
moreover, a tree generated by Prim's algo at the kth iteration is a MST. (otherwise this simple greedy algo scheme would fail)

if T!=T', let ek(u,v) be the first edge in T that is not in T'. ek is chosen at the kth iteration of Prim's algo.
in other words, after (k-1)th iteration, T(k-1) and T'(k-1) are the idential.
after (k-1)th iteration, u is in S, v is in V-S.
now, since ek(u,v) is not in T', there must be an edge(e,x) chosen by T'

let P be the path from u to v in T'. within P, there must be edge(u,x)

it must be  ek(u,v) <= edge(u,x)  because otherwise Prim's algo wouldn't have chosen ek(u,v)
this applies to every iteration, so the total weight of T must be less than or equal to T' but T' is a MST thus T=T'

(ref)
http://math.wikia.com/wiki/Proof_of_Prim's_algorithm
http://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture10/Lecture10.pdf
http://www.cs.uku.fi/~kilpelai/ASA/Prim_correctness.txt
http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2018%20-%20Greedy%20Technique%20and%20Prim%20Algorithm.htm

#############################
####    kruskal's algo   ####
#############################

to be written.

1. 2014-08-18 21:08:45 |
2. Category : algo
3. Page View: