**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 Tree
**Example:**

** 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)**

Topic : Minimum cost spanning trees | Kruskal’s Algorithms

wheres the prim’s part?