Clicker Questions - 20-Prim
You are given an undirected graph with the following adjacency matrix.
Suppose we use Prim’s algorithm to determine the minimum spanning tree of this graph, and we start building the three with node A.
Question 1: What is the second node that we put onto the minimum spanning tree?
Answer
We start by putting Node A onto the spanning tree, and then we put A's edges onto the multimap, ordered by smallest edge weight. That means the multimap will be:[ 12, D ] [ 91, B ]We then pull the smallest node off the multimap and put it on the spanning tree. That is Node D.
Question 2: What is the third node that we put onto the minimum spanning tree?
Answer
When we process Node D, we don't update B's entry on the multmap, because DB has a larger weight. We do put G on the multimap, though. It becomes:[ 84, G ] [ 91, B ]We then pull the smallest node off the multimap and put it on the spanning tree. That is Node G.
Question 3: What is the fourth node that we put onto the minimum spanning tree?
Answer
We process Node G, which puts E and H onto the multimap. It becomes:[ 20, H ] [ 45, E ] [ 91, B ]We then pull the smallest node off the multimap and put it on the spanning tree. That is node H.
Question 4: After we put the fourth node onto the spanning tree and process its edges, what is the order of the nodes on the multimap (give your answer as node letters with no spaces with no spaces, such as “ABCD”).
Answer
We process Node H, which puts nodes F and I onto the multimap. Here's the multimap:[ 39, F ] [ 45, E ] [ 91, B ] [ 112, I ]So the answer is "FEBI".