Kruskal's Method

Yesterday, we watched a video about Prim's algorithm. What is the difference between how to start Prim versus what he just said in the video?

• They are exactly the same

• He just said with Kruskal we will start with any point and yesterday with Prim's algorithm we started with the least costly edge

• He just said with Kruskal we start with the least costly edge and yesterday with Prim's algorithm we started with any vertex

If there was another edge that was also a cost of 1, could we have picked that one instead?

• yes, if you have two of the same it doesn't matter which one you pick as long as it doesn't create a cycle

• no, if you pick the wrong one you would fail

Why were we able to select both edges with a cost of 2?

• Because they didn't create a cycle

• Because 2 comes after 1

Which edges does it look like he can select next? Select all that apply

• AB

• CD

• CF

• He cannot select 4 without creating a cycle

Why can't we use edge IG?

• It creates a cycle, which is not allowed in the definition of a tree

• Because it was 6 and we were still looking for 5

• It isn't long enough

Picking AH instead of BC would create a different minimum spanning tree

• True

• False

You are done finding a minimum spanning tree when:

• You have connected every vertex

• There are no cycles

• You used every edge