Minimum Spanning Tree: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
| Line 9: | Line 9: | ||
an MST for that graph. | an MST for that graph. | ||
== Greedy | == Approach: Greedy == | ||
The approach is to try to add the smallest edges as long as they do not | The approach is to try to add the smallest edges as long as they do not | ||
create a cycle; add an edge to the tree that is minimum across the cut | create a cycle; add an edge to the tree that is minimum across the cut | ||
of <math>T</math> vs. <math>V - T</math> | of <math>T</math> vs. <math>V - T</math> | ||
Given the MST of <math>V_{n - 1}</math>, the MST of <math>V</math> | |||
should be that of <math>V_{n-1}</math> plus the edge that connects to | |||
<math>v_n</math> that is the shortest. | |||
<math> | |||
OPT(n) = OPT(n-1) + min( (v_i, v_n) \in E ) | |||
</math> | |||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
Revision as of 01:21, 6 March 2024
A minimum spanning tree is
- a tree, meaning it has no cycle
- minimum, meaning it has minimum weight
- spanning, meaning it connects all nodes
MST Problem
The MST problem takes a connected graph and outputs an MST for that graph.
Approach: Greedy
The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of vs.
Given the MST of , the MST of should be that of plus the edge that connects to that is the shortest.
