TADM2E 6.11
From Algorithm Wiki
Revision as of 20:55, 11 April 2016 by GreatSalmon (talk | contribs) (Created page with "Start with an arbitrary vertex. Put the edges of this vertex in a min heap, where each node of the heap contains a value equal to the weight of the edge, and a list of destina...")
Start with an arbitrary vertex. Put the edges of this vertex in a min heap, where each node of the heap contains a value equal to the weight of the edge, and a list of destination vertices. While min heap is not empty, take out the min edge, remove the destination vertex from the list, and add the edge to the tree.
For each of the n vertices, we will extract the min edge from the heap. The heap has a size of k, and each extraction operation takes $ log(k) $ time. So total time will be $ O(n*log(k)) $
