Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionv [2012/03/01 01:44] – [Analyzing the Algorithms] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionv [2012/03/01 02:15] (current) – [Implementing Prim's Algorithm] mugabej
@@ Line 54: / Line 54: @@
 ==== Implementing Prim's Algorithm ====
-  *
+  * We need to decide which node //v// to add next to the set S at each time
+  * We maintain the attachment costs a(//v//) = min<sub> e = (u,v):u in S</sub> C<sub>e</sub> for each node //v// in V-S
+  * Keep the nodes in a Priority Queue(PQ) with a(//v//), the attachment costs, as the keys
+  * We use ** ExtractMin ** to extract the node //v// to add to S
+  * We use the ** ChangeKey ** operation to update the attachment costs
+  * The ** ExtractMin ** operation is performed n-1 times
+  * The ** ChangeKey ** operation is done at most once for each edge
+  * Thus using a PQ, we can implement Prim's algorithm in O(mlogn) time\\
+\\
+Implementation from our class' lecture:\\
+>>>>>>>>>>>>>>>>>>>>> for each (v ∈ V) a[v] = ∞
+>>>>>>>>>>>>>>>>>>>>> Initialize an empty priority queue Q
+>>>>>>>>>>>>>>>>>>>>> for each (v ∈ V) insert v onto Q
+>>>>>>>>>>>>>>>>>>>>> Initialize set of explored nodes S = φ
+>>>>>>>>>>>>>>>>>>>>> while (Q is not empty)
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> u = delete min element from Q
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> S = S ∪ { u }
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> for each (edge e = (u, v) incident to u)
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> if (v ∉ S) and (c<sub>e</sub> < a[v])
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>decrease priority a[v] to c<sub>e</sub>
+\\
+There are several applications of the Minimum Spanning Tree algorithms, many can be found in the book.\\
+This was by far the most interesting reading of the chapter!I give it a 9/10.