Define and give an example of a Minimum Cost Spanning Tree. Write atleast two differences between Kruskal's and Prim's Algorithms.

Spanning Tree

A spanning tree is the subgraph of an undirected connected graph.

Minimum Cost Spanning Tree

A minimum-weight tree in a weighted graph, which contains all of the graph's vertices.

or

A minimum spanning tree can be defined as the spanning tree in which the sum of the weights of the edge is minimum. The weight of the spanning tree is the sum of the weights given to the edges of the spanning tree

Example

Prim's Algorithm

Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.

1.     First, we have to initialize an MST(minimum spanning tree) with the randomly chosen vertex

2.    Now, we have to find all the edges connecting the tree to the new vertices in the above step. From the found edges, select the minimum edge and add it to the tree. 

3.    If the edge end then goes to all previous vertexes find to select the minimum edge and add it to the tree.

4.    Repeat step 2 until the minimum cost spanning tree is formed.

	Kruskal’s Algorithm	Prim’s Algorithm
Principle	Based on generic minimum cost spanning tree algorithm	A special case of generic minimum cost spanning tree algorithm.
Operation	Operates on a single set of edges in the graph	Operates on two disjoint sets of edges in the graph
Running Time	O(E log E) where E is the number of edges in the graph	O(E log V), which is asymptotically the same as Kruskal’s algorithm
	It starts to build the Minimum Spanning Tree from the vertex carrying minimum weight in the graph.	It starts to build the Minimum Spanning Tree from any vertex in the graph.