CS211: Design and Analysis of Algorithms

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 4.5. The Minimum Spanning Tree Problem ======

  * A Spanning Tree is a tree that spans all the nodes in a graph
  * Given a connected graph G = (V, E) with positive edge weights c<sub>e</sub>, a Minimum Spanning Tree is a subset of the edges T ⊆ E such that T is a spanning tree whose sum of edge weights is minimized.

== Problem To be solved ==

  * We need to find the cheapest spanning tree of the graph, which is called the Minimum Spanning Tree as mentioned above

==== Designing the algorithm ====

Three simple algorithms that efficiently finds the Minimum Spanning Tree:\\

=== Prim's algorithm ===

  * Start with some root node s and greedily grow a tree T from s outward
  * At each step, add the cheapest edge e to T that has exactly one endpoint in T
  * 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\\
        * Initially S = {s}, s the root node\\
        * 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>\\
         * Also add the edge e =(u,v) that satisfies the above formula.

=== Kruskal's algorithm ===

  * Start with T = φ,thus T = an empty tree
  * Consider edges in ascending order of cost
  * Insert edge e in T as long as e doesn't create a cycle when added
  * if e creates a cycle, we ignore it and move on to the next node


=== 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.