A spanning tree of any graph is only a subgraph that keeps all the vertices and is a tree (having no cycle). A graph might have many spanning trees.

Figure: A Graph

Figure: Spanning trees of the Graph of above graph

Let the graph of given graph. It's spanning trees are shown in Figure.

Now, if the graph is weighted graph (length related with each edge). The weight of the tree is only the sum of weights of its edges. Clearly, distinct spanning trees have different weights or lengths. Our objective is to determine the minimum length (weight) spanning tree.

Imagine, we have a group of islands that we desire to link with bridges so that it is possible to travel from one island to any other in the group. The set of bridges that will enable one to travel from any island to any other at minimum capital cost to the government will be the minimum cost spanning tree.