Graphs:   Min' Spanning Tree (Prim):     Introduction

• Saw various kinds of Graph and examples,   now . . .
  
  
• Minimum spanning tree (MST) of a weighted undirected graph, G.
  
  
  • An MST is connected, contains all vertices and a subset of edges of G.
    
    
• Note, cycles are redundant for connectivity.
  
  
• Spanning tree is non-redundant, cheaper.  Minimum one = cheapest.
  
  
• (NB. redundancy may in fact be useful for reliability.)

MST . . .

• Minimum Spanning Tree in red,   NB. not necessarily unique.
  
  
• Connected, no cycles, minimal (cheapest, lightest). Can you do better?
  
  
• How . . .

Prim's MST Algorithm

• Very similar to Dijkstra's   s' s' shortest paths algorithm
  
  which was optimising [what_______________________?] criterion.
  
  
• Also a dynamic programming, greedy algorithm.
  
  
• Prim's MST alg' starts with a small tree < {v₁}, { } >
  
  
• It iterates, adding the "undone" vertex that is closest to the tree.
  
  
• Does this   | V | - 1   times.

Start with the tree  < { v₁ }, { } >.   Vertex v₄ is closest to tree . . .

done := {v1}   --initial Tree is <{v1},{}>

for vertex i in V-{v1}
   T[i] := E[1,i]     --direct edges else "infinity"    [*]
end for

loop |V|-1 times
-- INV: {T[v]|v in done} represents a min' spanning Tree
-- of the nodes in done and {T[u]|u not in done} contains
-- the shortest known distances from the (sub-)spanning Tree
-- to such vertices u.

   find closest vertex to (sub-)spanning Tree in V - done;

   done +:= {closest};
   add `closest' and `edge T[closest]' to (sub-)spanning Tree;

   for vertex j in V - done
      T[j] := min(T[j],   --update knowledge on paths,
                  E[closest,j])      --perhaps better? [*]
   end for
end loop -- run demo',  cf. Dijkstra's

Proof of Prim's MST algorithm:

• The outer loop invariant is true initially when 'done' contains one vertex.
  
  
• Suppose the algorithm chooses closest vertex v_c, and edge (v_t, v_c), during an iteration.
  
  
• v_c must be connected to v₁ somehow in a final MST.
  Either {v₁, ..., v_t, v_c} is an optimal way or there is a cheaper way, but
  
  
  • that cannot involve any vertex, v_u, not currently in the tree, and edge (v_t',v_u), because |(v_t, v_c)| <= |(v_t', v_u)|, and
    
    
  • there cannot be a cheaper edge from the (sub) tree to v_c because the algorithm picks the cheapest edge from the tree to a vertex in V-done.
    
    
  So it is optimal.
  
  
• Termination - obvious.

Hint: A sub-tree of a (partial) MST must itself be a MST of those vertices that it spans.

Graphs:   Min' Spanning Tree (Prim):   Summary

• Prims' algorithm takes O( | V |² )-time.
  
  
• Very similar to Dijkstra's single-source shortest paths algorithm,
  
  
• greedy, dynamic programming,
  
  
• subtly different optimisation criterion to Dijkstra's.
  
  
• Homework: compare Dijkstra's (paths) algorithm and Prim's MST algorithm; make sure you understand their similarities and their differences.