Question 8: Spanning trees [10]

Suppose the following MST algorithm was used in one adjacency-list graph implementation and one adjacency-matrix graph implementation.

Compare the best case performance of the two versions, and compare the worst case performance of the two versions.

initialize every node's "in-mst" flag to false
create a heap of edges, initially empty
create a queue of mst nodes, initially empty
pick a starting node and mark it as in the mst
   and treat it as our current node
keep track of the number of nodes in our mst,
   initially 1 (counting our starting node)
while the size of the queue is less than the total
   number of nodes in the graph, repeat the following:
      mark the current node as part of the mst
      put each of its edges in the heap
      find the top heap edge that connects an mst node
           to a non-mst node (quit if there is none)
      add the selected edge to the mst
      increment the size of the mst
      treat our new current nodes as the one which the
         selected edge adds to the tree