Min Span

Minimum Spanning Tree, Kruskal’s and Prim’s Algorithms, Applications in Networking Submitted by: Hardik Parikh Soujanya Soni

What is Tree ?

OverView • • • • • • • •

Tree definition Spanning Trees Minimum Spanning Trees Kruskal’s and Prim’s algorithms for Minimum Spanning Trees Comparison & Analysis of Kruskal’s and Prim’s Algorithms Why MST ???? Applications of MST in Sensor Networks Conclusion

Trees •Example: Are the following graphs trees?

• Definition: A tree is a connected undirected graph with no simple circuits. • Since a tree cannot have a simple circuit, a tree cannot contain multiple edges or loops. • Therefore, any tree must be a simple graph.

No.

Yes.

Yes.

No.

• Theorem: An undirected graph is a tree if and only if there is a unique simple path between any of its vertices.

Spanning Trees A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees

Spanning Tree properties: On a connected graph G=(V, E), a spanning tree:

• • • •

is a connected subgraph acyclic is a tree (|E| = |V| - 1) contains all vertices of G (spanning)

1

Minimum Spanning Trees

Spanning trees • Suppose you have a connected undirected graph – Connected: every node is reachable from every other node – Undirected: edges do not have an associated direction • ...then a spanning tree of the graph is a connected subgraph in which there are no cycles • Total of 16 different spanning trees for the graph below

The Minimum Spanning Tree for a given graph is the Spanning Tree of minimum cost for that graph.

•

Complete Graph

Minimum Spanning Tree

7 2

2 5

3

3 4 1

1

A connected, undirected graph

Four of the spanning trees of the graph

Minimum weight spanning tree (MST)

Finding Minimum Spanning Tree Algorithms :

On a weighted graph, A MST: • connects all vertices through edges with least weights.

• Kruskal’s and • Prim’s

• has w(T) ≤ w(T’) for every other spanning tree T’ in G • Adding one edge not in MST will create a cycle

Kruskal’s Algorithm

Kruskal’s algorithm Æ Edge first 1. Arrange all edges in a list (L) in nonnon-decreasing order 2. Select edges from L, and include that in set T, avoid cycle. 3. Repeat 3 until T becomes a tree that covers all vertices

15

8 13

13

1 14

16

12

2 7

5 4 12

16

14

3 14

15

14

6

{1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

{1,4}

16

{2,3}

16

2

Kruskal’s Algorithm 15

8 13

13

1 14

16

12

4 12

2 7

5

16

14

14

3 14

15

6

{1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

{1,4} {2,3}

Kruskal’s Algorithm {1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

16

{1,4}

16

16

{2,3}

16

8 13

14

8 13

13

1 14

16

12

4 12

2 7

5

16

14

14

3 14

15

6

{1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

{1,4} {2,3}

8 13

13

1 14

16

12

4 12

2 7

5

16

14

3 14

15

14

6

4 12

2

16

14

14

3 14

15

6

Kruskal’s Algorithm {1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

16

{1,4}

16

16

{2,3}

16

{1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

{1,4} {2,3}

15

8 13

14

16

12

4 12

2 7

5 13

1

Kruskal’s Algorithm 15

16

12

7

5 13

1

Kruskal’s Algorithm 15

15

16

14

14

3 14

15

6

Kruskal’s Algorithm {1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

16

{1,4}

16

16

{2,3}

16

15

8 13

13

1 14

16

12

4 12

2 7

5

16

14

3 14

15

14

6

3

Kruskal’s Algorithm 15

8

5

13

13 16

1 14

4

12

12

2 7

14

3

16

14

14 15

6

Skip {7,8} to avoid cycle

{1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

{1,4}

16

{2,3}

16

Kruskal’s Algorithm 8

8

5

13

13 16

1 14

12

12

2 7

4 14

3

16

14

14 15

6

MST is formed

{1,2}

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

{5,6}

14

{5,8}

15

{6,7}

15

{1,4}

16

{2,3}

16

15 13

14

12

Start from any arbitrary vertex

7

16

14

14

14 15

6

12

{3,4}

12

{1,8}

13

{4,5}

13

{2,7}

14

{3,6}

14

{7,8}

14

Skip

{5,6}

14

Skip

{5,8}

15

{6,7}

15

{1,4}

16

{2,3}

16

ƒ Start form any arbitrary vertex ƒ Find the edge that has minimum weight form all known vertices ƒ Stop when the tree covers all vertices

Prim’s algorithm 15

8 1

16

14

7

5 13

4 12

2 6

3

16

{1,2}

Prim’s algorithm

3 14

15

14

Skip {5,6} to avoid cycle

1 14

4 12

2

13

4 12

2 7

16

16

12

Skip

13

1 14

5

13

1

Prim’s algorithm 8

5

13

Kruskal’s Algorithm 15

15

16

14

3 14

15

1 14

12

2 6

The best choice is {1,2} What’s next?

Weight:12

4

Prim’s algorithm 15

8

5

8 13

13

1

16

14

12

2 7

4

16

14

1 14

12

3 14

15

Prim’s algorithm After {1,8} we may choose {2,7} or {7,8} There are more than one MST

6

Prim’s algorithm 8

5 16

14

4 12

2

16

7

15

5

14

Let’s choose {5,8} at this moment

12

2 6

7

The best choice is now {4,5}

14

Prim’s algorithm 8

5 1

16

4

7

16

12

3 14

15

12

2

16

14

12

3 14

15

7

5 4 12

2 6

Let’s choose {2, 7} at this moment

1

We are free to choose {5,8} or {6,7} but not {7,8} because we need to avoid cycle

2 6

7

8

5

14

15

8

1

16

14

4 12

2

16

14

7

15

14

4

12

3

The best choice is now {4,3}

2 6

7

5 13

1 14

8

5

14

3

15

8 13

13

1 14

2

14

4

Prim’s algorithm 15

8 13

14

13

13

1

3 14

16

13

13

1

8

Prim’s algorithm 15

8

1

7

Weight:12+13

5 13

What’s next?

2

15

8

The best choice is now {3,6} or {5,6}

1

16

4

14

2 7

1 14

16

15

12

3 7

4 12

2 6

5 13

14

3 14

A MST is formed Weight = 93

6

5

Prim’s algorithm – more complex 3

3

20 54

5

5

0

100

8

14

20 54

0 44

Prim’s algorithm – more complex

44

100

8

14

32

32

99

99 31

14

11 19

19

Prim’s algorithm 3

Prim’s algorithm 3

20 54

5

5

0

100

8

14

20 54

0 44

44

100

8

14

32

32

99

99 31

14

11 19

19

Prim’s algorithm 3

Prim’s algorithm 3

20 54

20 54

5

0

5

0

100

8

14

31

14

11

44

31

14

11

44

100

8

14

32

32

99

99 31

14 11

31

14 11

19

19

6

Prim’s algorithm 3

3

20 54

5

5

0

100

8

14

20 54

0 44

Prim’s algorithm

44

100

8

14

32

32

99

99 31

14

11 19

19

Compare Prim and Kruskal

Prim’s algorithm 3

20 54

5

0 44

MST is formed

100

8

14

31

14

11

32 99

Both have the same output Æ MST Kruskal’s begins with forest and merge into a tree Prim’s always stays as a tree If you don’t know all the weight on edges Æ use Prim’s algorithm • If you only need partial solution on the graph Æ use Prim’s algorithm

• • • •

31

14 11 19

Compare Prim and Kruskal Complexity Kruskal: O(NlogN) comparison sort for edges Prim: O(NlogN) search the least weight edge for every vertice

Analysis of Kruskal's Algorithm Running Time = O(m log n)

(m = edges, n = nodes)

Testing if an edge creates a cycle can be slow unless a complicated data structure called a “union-find” structure is used. It usually only has to check a small fraction of the edges, but in some cases (like if there was a vertex connected to the graph by only one edge and it was the longest edge) it would have to check all the edges. This algorithm works best, of course, if the number of edges is kept to a minimum.

7

Analysis of Prim's Algorithm Running Time = O(m + n log n)

(m = edges, n = nodes)

If a heap is not used, the run time will be O(n^2) instead of O(m + n log n). However, using a heap complicates the code since you’re complicating the data structure. A Fibonacci heap is the best kind of heap to use, but again, it complicates the code. Unlike Kruskal’s, it doesn’t need to see all of the graph at once. It can deal with it one piece at a time. It also doesn’t need to worry if adding an edge will create a cycle since this algorithm deals primarily with the nodes, and not the edges.

Why do we need MST? • a reasonable way for clustering points in space into natural groups • can be used to give approximate solutions to hard problems

For this algorithm the number of nodes needs to be kept to a minimum in addition to the number of edges. For small graphs, the edges matter more, while for large graphs the number of nodes matters more.

Minimizing costs • Suppose you want to provide solution to : – electric power, Water, telephone lines, network setup • To minimize cost, you could connect locations using MST • However, MST is not necessary the shortest path and it does not apply to cycle

Applications of MST in Sensor Neworks • Given a set of sensor nodes and data sink in a plane, the transmission power of each sensor node is adjusted in such a manner (using minimum spanning trees in terms of Euclidian distances), that a tree is formed from all sensor nodes to the sink and total transmission power of all sensor nodes is minimum.

MST don’t solve TSP • Travel salesman problem (TSP) can not be solved by MST : Æ salesman needs to go home (what’s the cost going home?) Æ TSP is a cycle Æ Use MST to approximate Æ solve TSP by exhaustive approach try every permutation on cyclic graph

Conclusion

Kruskal’s has better running times if the number of edges is low, while Prim’s has a better running time if both the number of edges and the number of nodes are low.

So, of course, the best algorithm depends on the graph and if you want to bear the cost of complex data structures.

8

Questions

The End

?

Thank you

9