kruskals and prims algo

Minimum- Spanning Trees : 

Minimum-Spanning Trees Minimum- Spanning Trees 1. Concrete example: computer connection 2. Definition of a Minimum- Spanning Tree 3. The Crucial Fact about Minimum- Spanning Trees 4. Algorithms to find Minimum- Spanning Trees - Kruskal‘s Algorithm - Prim‘s Algorithm - Barůvka‘s Algorithm

Concrete example : 

Minimum-Spanning Trees Imagine: You wish to connect all the computers in an office building using the least amount of cable a weighted graph problem !! Each vertex in a graph G represents a computer Each edge represents the amount of cable needed to connect all computers Concrete example

Slide 3: 

Minimum-Spanning Tree We are interested in: Finding a tree T that contains all the vertices of a graph G spanning tree and has the least total weight over all such trees minimum-spanning tree (MST)

The Crucial Fact about MST : 

Crucial Fact min-weight “bridge“ edge The Crucial Fact about MST e

Slide 5: 

Crucial Fact The Crucial Fact about MST - The basis of the following algorithms Proposition: Let G = (V,E) be a weighted graph, and let and be two disjoint nonempty sets such that . Furthermore, let e be an edge with minimum weight from among those with one vertex in and the other in . There is a minimum- spanning tree T that has e as one of its edges.

Slide 6: 

Crucial Fact The Crucial Fact about MST - The basis of the following algorithms Justification: There is no minimum- spanning tree that has e as one of of its edges. The addition of e must create a cycle. There exists an edge f (one endpoint in the other in ). Choose: . By removing f from , a spanning tree is created, whose total weight is no more than before. A new MSTcontaining e Contradiction!!! There is a MST containing e after all!!!

MST-Algorithms : 

MST-Algorithms Input: A weighted connected graph G = (V,E) with n vertices and m edges Output: A minimum- spanning tree T MST-Algorithms

Kruskal‘s Algorithm : 

Kruskal's Algorithm Kruskal‘s Algorithm Each vertex is in its own cluster 2. Take the edge e with the smallest weight - if e connects two vertices in different clusters, then e is added to the MST and the two clusters, which are connected by e, are merged into a single cluster - if e connects two vertices, which are already in the same cluster, ignore it 3. Continue until n-1 edges were selected

Slide 9: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 10: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 11: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 12: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 13: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 14: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2 cycle!!

Slide 15: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 16: 

Kruskal's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 17: 

Kruskal's Algorithm C F E A B D 3 2 1 2 2 minimum- spanning tree

The correctness of Kruskal‘s Algorithm : 

Kruskal's Algorithm The correctness of Kruskal‘s Algorithm Crucial Fact about MSTs Running time: O ( m log n ) By implementing queue Q as a heap, Q could be initialized in O ( m ) time and a vertex could be extracted in each iteration in O ( log n ) time

Code Fragment : 

Kruskal's Algorithm Input: A weighted connected graph G with n vertices and m edges Output: A minimum-spanning tree T for G for each vertex v in G do Define a cluster C(v)  {v}. Initialize a priority queue Q to contain all edges in G, using weights as keys. T   while Q   do Extract (and remove) from Q an edge (v,u) with smallest weight. Let C(v) be the cluster containing v, and let C(u) be the cluster containing u. if C(v)  C(u) then Add edge (v,u) to T. Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u). return tree T Code Fragment

Prim‘s Algorithm : 

Prim's Algorithm Prim‘s Algorithm All vertices are marked as not visited 2. Any vertex v you like is chosen as starting vertex and is marked as visited (define a cluster C) The smallest- weighted edge e = (v,u), which connects one vertex v inside the cluster C with another vertex u outside of C, is chosen and is added to the MST. 4. The process is repeated until a spanning tree is formed

Slide 21: 

Prim's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 22: 

Prim's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2

Slide 23: 

Prim's Algorithm C F E A B D 5 6 4 3 4 2 1 2 3 2 We could delete these edges because of Dijkstra‘s label D[u] for each vertex outside of the cluster

Slide 24: 

Prim's Algorithm C F E A B D 3 4 2 1 2 3 2

Slide 25: 

Prim's Algorithm C F E A B D 3 2 1 2 3 2

Slide 26: 

Prim's Algorithm C F E A B D 3 2 1 2 2 3

Slide 27: 

Prim's Algorithm C F E A B D 3 2 1 2 2

Slide 28: 

Prim's Algorithm C F E A B D 3 2 1 2 2

Slide 29: 

Prim's Algorithm C F E A B D 3 2 1 2 2 minimum- spanning tree

The correctness of Prim‘s Algorithm : 

Prim's Algorithm The correctness of Prim‘s Algorithm Crucial Fact about MSTs Running time: O ( m log n ) By implementing queue Q as a heap, Q could be initialized in O ( m ) time and a vertex could be extracted in each iteration in O ( log n ) time