Minimum Spanning Tree: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
| Line 4: | Line 4: | ||
* spanning, meaning it connects all nodes | * spanning, meaning it connects all nodes | ||
= MST Problem = | |||
The '''MST problem''' takes a connected graph <math>G</math> and outputs | |||
an MST for that graph. | |||
== Greedy Approach == | |||
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 <math>T</math> vs. <math>V - T</math> | |||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
Revision as of 01:13, 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.
Greedy Approach
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.
