CS计算机代考程序代写 data structure algorithm Graph Processing Algorithms

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.