Minimum cost spanning trees
- A spanning tree of a graph is just a sub graph that contains all the vertices and is a tree.
- Thus a spanning tree spans over all vertices of the graph
- A minimum cost spanning tree of a weighted graph is a spanning tree of the graph with minimum total weight
- Let G=(V,E) be a connected, undirected graph. For each edge (u,v)∈E, we have a weight w(u,v) specifying the cost to connect u and v. We wish to find an acyclic subset T ⊆ E that connects all of the vertices and whose total weight is minimized.
- This problem can be solved by Greedy method
- At each step we determine an edge (u,v) that can be added into a solution vector in such a way that the subset formed in A will give a Minimum Spanning Tree with minimum weight.
- The each edge collected at A is called safe edge.
- Two algorithms widely used for Minimum cost spanning trees are:
- Kruskal’s Algorithm
- Prim’s Algorithm
Minimum cost spanning trees using Kruskal’s Algorithm
- Edges of the graph are sorted in non-decreasing order by weight
- Edges are considered one at a time for inclusion into a tree T
- If adding an edge (v, w) to T would create a cycle then discard (v, w) else add (v, w) to T .
T may not be a tree at all stages in the algorithm. In fact, it will be a forest of trees
- Disjoint sets are widely used to implement this algorithm. By applying UNION and FIND algorithms we can construct the Minimum Spanning TreeExample:
Total Cost = 105
5.An algorithm for generating minimum cost spanning tree is given below:
6.Time Complexity of Kruskal’s Algorithm is O(E log E)