Minimum Spanning Tree quiz



Consider the cut {2, 3, 6}. What is the minimum weight edge crossing the cut?

0-7 (0.16)
2-3 (0.17)
0-2 (0.26)
1-2 (0.36)

How many distinct Edge objects are there in the adjacency-lists representation of an edge-weighted graph with V vertices and E edges?

V
E
V + E
2E

Assume that we're running Kruskal's algorithm, and have only added the edge 0-7 so far. Which edge will be selected next?

2-3 (0.17)
1-7 (0.19)
0-2 (0.26)
5-7 (0.28)
1-3 (0.29)

Assume that we're running the lazy version of Prim's algorithm, and have only added the edge 0-7 so far. Which edge will be selected next?

2-3 (0.17)
1-7 (0.19)
0-2 (0.26)
5-7 (0.28)
1-3 (0.29)

Assume that we're running the eager version of Prim's algorithm, and have only added the edge 0-7 so far. Which edge will be selected next?

2-3 (0.17)
1-7 (0.19)
0-2 (0.26)
5-7 (0.28)
1-3 (0.29)

Assume that we're running one of our three MST algorithms, and have added the edge 0-7. How many edges are on the PQ for Kruskal's algorithm? Lazy Prim's algorithm? Eager Prim's algorithm? There are 16 total edges in the graph.

15, 7, 5
15, 15, 7
15, 15, 5
15, 7, 7
7, 7, 7