Next: 0.4.5.1 Prim's Algorithm
Up: 0.4 Graph Algorithms
Previous: 0.4.4.2 Source Code
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
0.4.5 Spanning Trees
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
In this section we explore several algorithms for finding
minimal spanning trees in graphs.