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.
