Let G = (V,E) be a connected, undirected, weighted graph. Our aim is to find a tree that "touches" all the vertices, using a subset of the edges of the original graph. This is called a spanning tree.
A graph could have more than one spanning tree. If the edges have weights (costs), the aim is to find a spanning tree for which the sum of the weights is minimum. This is called a minimum cost spanning tree.
G Tree 1 Tree 2 Tree 3 ...
o o o o
7 / \ 8 7 / 7 / \ 8
/ 6 \ / / 6 6 \
o-----o o o o-----o o-----o ...
\ / \ / / \
2 \ / 5 2 \ / 5 / 5 2 \
o o o o
Cost = 14 Cost = 18 Cost = 16
How do we find the minimum cost spanning tree? There are two standard algorithms.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky