Graph Processing Algorithms
Data Structures and Abstractions
Minimum Spanning Tree Algorithms
Lecture 34
*
MST versus SPT
The SPT problem of the previous lecture involved finding the shortest path from a single vertex to every other vertex.
The MST problem involves finding the shortest way to connect all the vertices to each other, using any vertex as a starting point.
Both apply to weighted graphs only.
The SPT is different for each starting vertex, the MST is the same no matter which vertex you start at.
*
Minimum Spanning Trees
The starting point of an MST is irrelevant: all three of the trees below are equivalent and represent the MST of the same graph.
*
MST Algorithms
There is much continuing research in this area.
All algorithms have advantages and disadvantages.
All algorithms are more or less efficient depending on the type of graph being processed.
The choice of data structure and programming language also affects the speed.
We will look at two algorithms: Prim’s, Kruskal’s and point out another one by Boruvka.
*
Prim’s Algorithm (animation)
PrimsMST
Pick any vertex and put it in the MST
FOR V-1 times
Add the shortest edge from a vertex already in the
MST to one outside the MST
ENDFOR
END PrimsMST
0
1
0
1
2
3
4
5
6
7
2
4
3
7
5
6
END
0
1
2
3
4
5
6
7
87
91
138
60
125
172
70
102
144
205
*
Kruskal’s Algorithm (animation)
KruskalMST
Sort the edges from shortest to longest
LOOP for each edge from shortest to longest AND edges added < V-1
Add the edge to the MST if it does not form a cycle with
previously added edge
END KruskalMST
0
1
0
1
2
3
4
5
6
7
2
4
3
5
7
6
END
Note that this tree is topgraphically the same as the previous one.
0
1
2
3
4
5
6
7
87
91
138
60
125
172
70
102
144
205
*
Costs
The algorithms will all run faster in some circumstances.
There is no algorithm that is always fastest.
The faster the algorithm, generally the harder it is to code, and therefore the more prone to error.
There is no algorithm that can guarantee linear time.
Algorithm Cost Comment
Prim’s O(V2) Optimal for dense graphs
Kruskal’s O(E log(E)) The highest cost is in the sorting
Boruvka’s O(E log(V)) This is a conservative upper bound
*
Other Examples
Make sure you can draw, by hand, an MST using each of these algorithms. The Graph program will allow you to check your answers.
*
Readings
Textbook Chapter on Graphs.
Reference book, Introduction to Algorithms. Part on Graph Algorithms contains a number of chapters on graph algorithms. Please read for further study. The lecture notes and textbook is sufficient for this unit. The reference book would give more details.