next up previous contents index Search
Next: Prim's Algorithm Up: 0.4 Graph Algorithms Previous: Source Code

0.4.5 Spanning Trees

A spanning tree in a graph is a tree that visits every node in the graph. Recall that a tree is a set of nodes and edges that has a single root node and no circuits.      

In many graphs each edge has an associated weight or cost. Such graphs are called weighted graphs. Often in     weighted graphs we want to find a spanning tree of minimal cost.

In this section we explore several algorithms for finding minimal spanning trees in graphs.

Scott Gasch