English 字幕

← 15-05 Finding A Minimum Spanning Tree Solution



Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. Now how do you go about finding a solution if you don't have an algorithm for it?
  2. Well, first of all, this edge here costs just 1, so we probably want to take that.
  3. Then we have a lot of edges that just have a weight of 2,
  4. and, of course, they have been arranged in a way that is very beneficial for us here
  5. because we can actually put them all into the tree,
  6. and we almost have a spanning tree here.
  7. There's just one vertex missing, which we still need to connect to that tree here.
  8. And the cheapest way to do that is to use this one edge down here, of course,
  9. using 4 instead of this one here which would use 6.
  10. So this is a minimum spanning tree for this graph, and this has a total weight of
  11. 2+2+1+2+2+4, which is a total of 13.