CSE100 Lab 11-Minimum Spanning Tree Solved

Minimum Spanning Tree
Description In the Minimum Spanning Tree problem, we are given as input an undirected graph G = (V,E) together with weight w(u,v) on each edge (u,v) ∈ E. The goal is to find a minimum spanning tree for G. Recall that we learned two algorithms, Kruskal’s and Prim’s in class. In this assignment, you are asked to implement Prim’s algorithm. The following is a pseudo-code of Prim’s algorithm.

Initialize a min-priority queue Q. for all u ∈ V do

u.key = ∞.

u.π = NIL.

Insert (Q,u).

end for

Decrease-key(Q,r,0).

while Q 6= ∅ do

u = Extract-Min(Q).

for all v ∈ Adj[u] do if v ∈ Q and w(u,v) < v.key then

v.π = u.

Decrease-Key(Q,v,w(u,v)).

end if

end for

end while

Input The input is G, w, and r, where r is an arbitrary vertex the user can specify as root. The input has the following format. There are two integers on the first line. The first integer represents the number of vertices, |V |. The second integer is the number of edges, |E|. Vertices are indexed by 0,1,...,|V | − 1. Each of the following |E| lines has three integers u,v,w(u,v) representing an edge (u,v) with weight w(u,v). Use vertex 0 as the root r.

Output The above pseudo-code stores the MST by π, where v.π = u means that u is v’s unique parent; here, r.π = NIL since r has no parent. Output the MST by outputting the π value of a vertex in each line, in the order 1,2,...,|V | − 1. (Do not output the root’s parent.) Implementation Issues Prim’s algorithm requires a min-priority queue that supports the DecreaseKey operation which is not supported by the standard C++ priority queue. You are allowed to use an “inefficient” priority queue that supports each operation in O(|V |) time. Such an inefficient priority queue can be easily implemented using an array. Then, the running time of your implementation is roughly O(|E||V |). However, you may still use the C++ priority queue with a simple “invalidation trick” and have your code to run in O(|E|log|V |). Instead of decreasing an element’s key, just mark the element as invalid and push a new (valid) element with the new key value to the queue. Then you just have to be careful when extracting a minimum element because what you really want is a minimum element that is valid. So extracting a valid min element could take a few iterations. However, at any point in time, the priority queue has at most O(|E|) elements, so each ExtractMin operation takes O(log|E|) = O(log|V |) time. Since you extract minimum elements at most O(|E|) times, you only need O(|E|log|V |) time for extracting valid min elements. To use invalidation trick, you just need to maintain a boolean variable for each vertex to track if it is included in the current MST: when you extract a vertex from the min priority queue, it is valid only if it is not yet part of the current MST.

Example of input and output

Input

9

14

0 1 40

0  7 85

1  2 80

1  7 110

2  3 70

2 5 45

2  8 22

3  4 90

3  5 140

4  5 100

5  6 25

6  7 10

6  8 60

7  8 75

(The input is a graph with weights given per edge.)

Output

0

1

2

3

2

5

6

2

Here, the first number refers to the parent of vertex 1, and the second number to the parent of vertex 2, and so on. Note that every line is followed by an enter key.

See the lab guidelines for submission/grading, etc., which can be found in Files/Labs.