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
Ce - cost of edge e ∈ E
Note :
- Its ok if edge costs are negative (opposite to djikstra’s algo)
- 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
- G cotnains path from any 1 node to other node.
- 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