Prim and Kruskal in Python

Questions 1 to 5 of 8

1. 1. Prim's algorithm is run with an adjacency matrix instead of a heap, on a graph with V vertices. What is its running time?

   O(V log V)O(V^2)O(E log V)O(V^3)
2. 2. The sample graph has 5 offices. How many cables does a minimum spanning tree on it have?

   Type a number.

3. 3. Prim's algorithm pops a cable whose far end is already in the tree. Why does it skip that cable? ``python while heap and len(chosen) < n - 1: e = heapq.heappop(heap) if in_tree[e.v]: continue ``

   Its cost is always higher than the cables already chosen, so it cannot help the totalThe heap cannot hold two cables that touch the same officeTaking it would close a cycle, so the result would no longer be a tree and the total would be wrongThe cable has no weight, so it adds nothing to the total
4. 4. In the adjacency matrix version of Prim, why is a missing edge stored as math.inf instead of 0?

   Prim picks the cheapest key, so a 0 for a missing edge would be chosen first and the total would be wrongA 0 would make the matrix too large to store in memorymath.inf is the only value Python lets a list holdPrim always picks the largest key first, so a 0 would never be chosen
5. 5. Put these steps of Prim's algorithm with a heap in the correct order.

   Use the arrows to put the steps in order.

   1. 1.Pop the cheapest cable from the heap↑↓
   2. 2.Stop when the tree holds n - 1 cables↑↓
   3. 3.If its far end is outside the tree, add that end and push the cables that leave it↑↓
   4. 4.Start a tree with vertex 0 and push its cables onto a heap↑↓