Prim and Kruskal

Questions 1 to 5 of 8

1. 1. A complete graph has one edge between every pair of vertices. How many edges does a complete graph with 500 vertices have?

   Type a number.

2. 2. In the lesson's timing run on a sparse graph with 200000 vertices and 600000 edges, which method was faster, and by roughly how much?

   Prim, about 30 percent fasterKruskal, about 30 percent fasterKruskal, about five times fasterThey took the same time
3. 3. A Prim implementation declares std::priority_queue<Item> heap; and leaves out std::greater<>. Run on the small example from this lesson, what total does it print?

   261113-1
4. 4. Kruskal calls dsu.unite(a, b) and gets false. What does that mean?

   The edge's two ends are in different trees, so Kruskal adds the edgeThe edge has weight 0, so Kruskal ignores itThe graph is not connected, so Kruskal stops and returns -1The edge's two ends are already in one tree, so adding it would close a loop, and Kruskal skips it
5. 5. Put these steps of Kruskal's algorithm in the order the code runs them, for one pass over the edges.

   Use the arrows to put the steps in order.

   1. 1.Take the next edge from the sorted list↑↓
   2. 2.If unite returned true, add the edge's weight to the total↑↓
   3. 3.Call unite on the edge's two ends↑↓
   4. 4.Sort every edge by weight, cheapest first↑↓