Min Spanning Tree

АА
by Аида Адамова1 view·Updated Mar 4, 2022
Create your own

Chapters

Audio TranscriptAuto-generated

  1. um Hello everyone today. I am going to tell you about the minimum spanning tree.
  2. So let's move to its meaning first.
  3. So what is the spanning tree itself in general?
  4. A spanning tree is a subset of graph tree which has
  5. all the virtues is covered with minimum possible number of ages
  6. and the spanning tree does not have cycles and it cannot be disconnected.
  7. So what is the minimum spanning tree?
  8. Let's understand this through a comparison here.
  9. You can see the underrated graph, the spanning tree and the minimum spanning tree.
  10. Um The cost of the spanning tree is the sum of ways
  11. of all the ages in the tree.
  12. These are the weights.
  13. There can and there can be many spanish trees,
  14. minimum spanning tree is a spanning tree where the
  15. cost is minimum among all the spanning trees.
  16. Like this is a spanning tree
  17. and this is all spanning tree.
  18. But if we um
  19. add those
  20. wait
  21. um
  22. the count will
  23. lower their.
  24. So this is the minimum spanning tree.
  25. Um there also can be many many many minimum spanning trees.
  26. You had two famous algorithms for finding the means penetrate
  27. its close calls and screams algorithm.
  28. Let's
  29. start with cruz coke
  30. algorithm.
  31. So how does it work? Let's find out by the example.
  32. There there is the example.
  33. And
  34. let's start with the first step.
  35. First of all, we are finding the age with the least weight and highlighted
  36. because this one
  37. is the least one.
  38. Next step is to finding the next age with the lowest weight and highlighted.
  39. So
  40. too is next
  41. low step,
  42. lowest weight
  43. and the first step.
  44. The third step.
  45. The last step we continue selecting the lowest ages
  46. until all notes are in the same tree.
  47. But
  48. we remember that
  49. we cannot have
  50. the cycle
  51. next spring's algorithm.
  52. How does it work? Let's find out by
  53. the this example.
  54. The first step is choosing a random notes and highlighted
  55. for this example. I'm doing note C
  56. then
  57. find all the all of the ages that go
  58. to um highlighted notes. For this example note C has three ages with weight
  59. 12 and three. Highlight the edge with the lowest weight,
  60. it's one. Yes.
  61. And next step look at all of the nodes highlighted so far
  62. in this example that A and C.
  63. Yes
  64. and highlight the age with lost weight.
  65. Not five, not four but
  66. so yes.
  67. And if you have more than
  68. one each with the same way big around the one.
  69. Next step, highlight the age with the lowest weight, choose from all of the wages,
  70. all of the ages that
  71. first come from all of the highlights notes and
  72. second reach a note that you haven't highlighted yet.
  73. And the 5/5 step is repeating steps five and six until you have
  74. no more on highlighted notes and in the end we will have such
  75. um a spanning tree
  76. minimum spanning tree.
  77. Okay,
  78. and
  79. the example,
  80. if the connecting tree helps to find the easiest path available,
  81. then
  82. in my opinion it can be represented in the following life examples.
  83. The first one example,
  84. um
  85. I have a list of places to go and I need
  86. to arrange them so that the shortest distance in the end
  87. I will pass.
  88. So,
  89. for example, this is home shop, um school and the library. Yes.
  90. So having designed the places as versaces and the distance at the weight of the age,
  91. I found this and learned the shortest way.
  92. Yes, this is the shortest way.
  93. So, and the second example is similar, but with the
  94. mm hmm.
  95. Home work, school home.
  96. Thank you for attention.