0.7 Graphs  (Page 6/21)

We can achieve this bound as follows: first sort the edges by weight using a comparison sort in O(E log E) time; this allows the step "remove an edge with minimum weight from S" to operate in constant time. Next, we use a disjoint-set data structure to keep track of which vertices are in which components. We need to perform O(E) operations, two 'find' operations and possibly one union for each edge. Even a simple disjoint-set data structure such as disjoint-set forests with union by rank can perform O(E) operations in O(E log V) time. Thus the total time is O(E log E) = O(E log V).

Provided that the edges are either already sorted or can be sorted in linear time (for example with counting sort or radix sort), the algorithm can use more sophisticated disjoint-set data structures to run in O(E α(V)) time, where α is the extremely slowly-growing inverse of the single-valued Ackermann function.

Example

Proof of correctness

Let P be a connected, weighted graph and let Y be the subgraph of P produced by the algorithm. Y cannot have a cycle, since the last edge added to that cycle would have been within one subtree and not between two different trees. Y cannot be disconnected, since the first encountered edge that joins two components of Y would have been added by the algorithm. Thus, Y is a spanning tree of P.

It remains to show that the spanning tree Y is minimal:

Let Y1 be a minimum spanning tree. If Y = Y1 then Y is a minimum spanning tree. Otherwise, let e be the first edge considered by the algorithm that is in Y but not in Y1. has a cycle, because you cannot add an edge to a spanning tree and still have a tree. This cycle contains another edge f which at the stage of the algorithm where e is added to Y, has not been considered. This is because otherwise e would not connect different trees but two branches of the same tree. Then is also a spanning tree. Its total weight is less than or equal to the total weight of Y1. This is because the algorithm visits e before f and therefore . If the weights are equal, we consider the next edge e which is in Y but not in Y1. If there is no edge left, the weight of Y is equal to the weight of Y1 although they consist of a different edge set and Y is also a minimum spanning tree. In the case where the weight of Y2 is less than the weight of Y1 we can conclude that Y1 is not a minimum spanning tree, and the assumption that there exist edges e, f with w(e)<w(f) is incorrect. And therefore Y is a minimum spanning tree (equal to Y1 or with a different edge set, but with same weight).