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

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

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

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

**) and**

*Breadth First Search***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,

**and**

*Prim's algorithm***.**

*Kruskal's algorithm*- 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)

## 0 comments:

## Post a Comment