Minimum Spanning tree MST

MST is used to connect a bunch of points to each other as cheaply as possible.

Applications

• clustering
• networking

Blazingly fast greedy algorithms
There are many greedy algorithm, but we will talk about 2:

• Prim's algo [1957, also djikstra' 1959] or Jarnic found it in 25 years earlier.
• Kruskal's algo[1956]. Will be using union find data-structure.

They are blazingly fast as they are almost close to linear time of number of edges:
O( m log n) time m = edges, n=vertices OR better O (|E| log |V|)

Problem definition

Input - undirected graph G (V,E) .

We assume adjacency list representations
C_e - cost of edge e ∈ E
Note :

1. Its ok if edge costs are negative (opposite to djikstra's algo)
2. We are using graph undirected graph. For directed graph, this problem is called optimal branching. Those algo are out of scope of this course

Output - Min. cost tree T subset of E that spans all vertices.

What do we mean by cost here?
cost here means summing up of all the edge costs or weights.

What do we mean by spanning tree - aka difference between spanning tree and minimum spanning tree?
Spanning tree properties
A sub-graph T of a connected graph G(V,E) is called a Spanning Tree if

• T has no cycles 
• if T includes every vertex of G i.e. V(T)=V(G)

If |V|=n and |E|=m, then the spanning tree of G must have n vertices and hence n-1 edges.
The resultant spanning ensure that the graph remain connected and further there is no circuit in it.

Two algorithms for finding a spanning tree are BFS (Breadth First Search) and DFS (Depth First Search).

Minimum spanning tree
  A minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.

Two algorithms commonly used, Prim's algorithm and Kruskal's algorithm.

Assumptions made

1. G cotnains path from any 1 node to other node.
2. Edge costs are distinct (though this is not very important as both prims and kruskal's algorithms work with non distinct edges)

Algorithms to solve MST

• Prim's algorithm
• Kruskal algorithm