Minimum Spanning Tree: Difference between revisions
From Rice Wiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Category:Algorithms]] | [[Category:Algorithms]] | ||
The input is an undirected, weighted graph <math>G</math> | |||
= Description = | |||
A '''minimum spanning tree''' is | |||
* a tree, meaning it has no cycle | |||
* minimum, meaning it has minimum weight | |||
* spanning, meaning it connects all nodes | |||
The input is an undirected, weighted graph <math>G</math>. The output is | |||
a tree that | |||
* connects all vertices | |||
* has minimum weight | |||
Revision as of 00:52, 6 March 2024
Description
A minimum spanning tree is
- a tree, meaning it has no cycle
- minimum, meaning it has minimum weight
- spanning, meaning it connects all nodes
The input is an undirected, weighted graph . The output is a tree that
- connects all vertices
- has minimum weight
