A tree is a graph which is connected and has no circuits. A tree that is created
from another graph by removing edges, but keeping a path to each vertex is called a
spanning tree. If the edges of a graph have weight, then we refer to graph as
a weighted graph.
A minimum spanning tree is a spanning tree for which the sum of the numbers associated
with the edges is a minimum.
To construct a minimum spanning tree from a weighted graph:
Step 1: Select any edge with minimum wieght.
Step 2: Select the next edge with minimum weight amount those not yet selected.
Step 3: Continue to choose edges of minimum weight from those not yet selected,
but make sure you not select any edge that forms a circiut.
Step 4: Repeat this process until the tree connects all the vertices of the
original graph.
If a graph is a tree with n vertices, then the number of edges
is n - 1.