Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Minimum-Cost Spanning Trees

The total cost of an edge-weighted undirected graph is simply the sum of the weights on all the edges in that graph. A minimum-cost spanning tree of a graph is a spanning tree of that graph that has the least total cost:

Definition (Minimal Spanning Tree)  Consider an edge-weighted, undirected, connected graph tex2html_wrap_inline70252, where C(v,w) represents the weight on edge tex2html_wrap_inline70510. The minimum spanning tree   of G is the spanning tree tex2html_wrap_inline71738 that has the smallest total cost,

displaymath71838

Figure gif shows edge-weighted graph tex2html_wrap_inline71850 together with its minimum-cost spanning tree tex2html_wrap_inline71852. In general, it is possible for a graph to have several different minimum-cost spanning trees. However, in this case there is only one.

   figure52152
Figure: An edge-weighted, undirected graph and a minimum-cost spanning tree.

The two sections that follow present two different algorithms for finding the minimum-cost spanning tree. Both algorithms are similar in that they build the tree one edge at a time.


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.