Below I give pseudocode for one implementating Kruskals algorithm using a priority queue (implemented as a binary min-heap0.

What is the running time of this implementation? Justify your answer. Note that I give you the running times of some of the lines in the pseudocode.

G is a graph with vertex set G.V and edge set G.E. H is the heap implementing the queue.

MST_Kruskal(G)

M = // M is a set of edges that represents the MST

V0 = // V0 is the set of all vertices not yet connected to the spanning tree.

for each vertex v G.V

V0 = V0 v // This step takes constant time per vertex

create a min-heap for the edges

for each edge e G.E

add e to the end of an array H of edges // This step takes constant time per edge

Build-Min-Heap( H )

while ( V0 != && heap H is not empty )

e = Heap-Extract-Min(H)

if either vertex incident on edge e is undiscovered

M = M e // This step takes constant time per vertex

Denote the vertices incident on e by v1 and v2.

if ( v1 V0 ) // This step takes constant time per vertex[1]

V0 = V0 v1 // This step takes constant time per vertex

if ( v2 V0 ) // This step takes constant time per vertex (as above)

V0 = V0 v2 // This step takes constant time per vertex

if ( V0 = )

return M

else

error: Graph is not connected, there is no spanning tree

[1] Assuming we use hashing, it will take amortized constant time.