Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Question 2.1

Here is just one example of steps for Kruskal's:

  1. Sort all edges by cost in ascending order.
  2. Choose the cheapest edge in our sorted collection. If adding the edge to our MST would not create a cycle, add it, otherwise discard.
  3. Repeat this process until we have a full MST, or $(V-1)$ edges in our MST.

Question 2.2

You can think of Prim's algorithm to be vertex-by-vertex while Kruskal's is edge-by-edge. In Prim's algorithm we want to maintain a tree over a set of vertices where each vertex remembers the cheapest edge that could connect it to that sat. At every step, connect the vertex that can be connected the cheapest. On the other hand, for Kruskal's we want to sort edges by weight (in increasing order). Add an edge if it connected new things to each other. Don't add an edge if it would create a cycle. Both Prim's and Kruskal's algorithm work to give us a minimum spanning tree.

Question 3

Question 3.1

In Kruskal's algorithm we want to pick the lowest cost edge (u, v) and add the edge to the MST if u and v are in different components, or on different "islands" as referred to in the lecture video. We're given the edges in sorted order so we go ahead and add the first four edges (A, D), (C, D), (B, E) and (D, E) as they all satisfy the above requirement.

Then looking at edge (A, B) we notice that they are in the same component, so we go ahead and skip that edge.

The next edge is (C, F) where C and F are both in different components so we can go ahead and add it to the MST.

The next edge (A, C) can be skipped because they are both in the same component.

Next (E, G) can be added. Since we've added $(V -1)$ edges to our MST, we're done, where $V$ is the number of vertices in the graph.

Question 3.2 and Question 3.3

The edge weights sum to 9 and this is the same as the answer we get by using Prim's algorithm. The answer is the same because they produce the same MST just by different means.

In general, Prim's and Kruskal's will find MSTs with the same globally minimal cost, but they might differ in which edges they use (if there are multiple edges with the same cost).