# kruskals and prims algo

Views:

Category: Education

## Presentation Description

Understanding kruskals and prims algorithms

## Presentation Transcript

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