Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionv [2012/03/01 01:17] – [Designing the algorithm] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionv [2012/03/01 02:15] (current) – [Implementing Prim's Algorithm] mugabej
@@ Line 11: / Line 11: @@
 Three simple algorithms that efficiently finds the Minimum Spanning Tree:\\
-\\
 === Prim's algorithm ===
@@ Line 18: / Line 18: @@
   * Similar to Dijkstra’s (but simpler)
   * So, in brief:
-    * >>>>>>>>>>>>>>>>>>> Maintain a set S ⊆ V ,the set on which we have constructed the spanning tree so far\\
+        * Maintain a set S ⊆ V ,the set on which we have constructed the spanning tree so far\\
-      >>>>>>>>>>>>>>>>>>> Initially S = {s}, s the root node\\
+        * Initially S = {s}, s the root node\\
-      >>>>>>>>>>>>>>>>>>> In each iteration:\\
+        * In each iteration:\\
-      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Grow S by one node, adding to S a node //v// whose cost = min<sub> e = (u,v):u in S</sub> C<sub>e</sub>\\
+         * Grow S by one node, adding to S a node //v// whose cost = min<sub> e = (u,v):u in S</sub> C<sub>e</sub>\\
-      >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Also add the edge e =(u,v) that satisfies the above formula.\\
+         * Also add the edge e =(u,v) that satisfies the above formula.
-=== Kruskal's algorithm. ===
-Ø Start with T = φ
+=== Kruskal's algorithm ===
-Ø Consider edges in ascending order of cost
-Ø Insert edge e in T unless doing so would create a cycle
+  * Start with T = φ,thus T = an empty tree
-• Reverse-Delete algorithm.
+  * Consider edges in ascending order of cost
-Ø Start with T = E
+  * Insert edge e in T as long as e doesn't create a cycle when added
-Ø Consider edges in descending order of cost
+  * if e creates a cycle, we ignore it and move on to the next node
-Ø Delete edge e from T unless doing so would disconnect T
+=== Reverse-Delete algorithm ===
+  * Start with T = E, E the set of all the nodes in the graph
+  * Consider edges in descending order of cost
+  * Delete edge e from T unless doing so would disconnect T
+==== Analyzing the Algorithms ====
+  * The **Cut Property **:
+    * Assume all edge costs are distinct --> The MST is unique
+    * Now, let S be any subset of nodes that is neither empty nor equal to V
+    * And let edge e = (v,w) be the minimum cost edge with one end in S and the other in V-S
+    * Then an spanning tree contains the edge e
+    * This straight-out-of-the-book statement is the cut property of the Minimum Spanning Tree.Proof:See book
+    * So, we can insert nodes in the MST as long as we don't create cycle when doing so.
+  * Prim's and Kruskal's algorithms produce a Minimum spanning tree of the graph G\\
+  * The **Cycle property**:
+    * Let C be any cycle, and let f be the maximum cost edge belonging to C
+    * Then MST does not contain f.
+    * So, we can delete a node from the MST as long as we don't disconnect our MST
+  * The Reverse-Delete Algorithm produces a Minimum Spanning Tree of the graph G
+==== 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.