Minimum Spanning Trees : MinimumSpanning 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 : MinimumSpanning 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: MinimumSpanning 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 minimumspanning tree
(MST)
The Crucial Fact about MST : Crucial Fact minweight
“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!!!
MSTAlgorithms : MSTAlgorithms Input: A weighted connected graph G = (V,E) with n vertices
and m edges
Output: A minimum spanning tree T MSTAlgorithms
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 n1 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 minimumspanning 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