Kruskal's
Notes
- Another MST algorithm
- Kruskal's takes a global approach, adding in the least expensive edge that belongs in the tree.
- Both can be implemented in O(E log2V)
- w is the weight function (ie edge costs)
- Kruskal's
- Kruskal's is stated in terms of sets.
- We form a collection of sets, each containing a single vertex.
- We then find the least expensive way to merge two sets by finding the lowest cost path between them.
- The trick is to find a data structure that makes this all work.
-
MST-KRUSKAL(G,w)
- A ← {}
- for each vertex v ∈ G.V
- MAKE-SET(v)
- Sort the edges of G.E smallest to largest
- for each edge e=(u,v) ∈ G.E smallest to largest
- S = FIND-SET(u), T= FIND-SET(v)
- if S ≠ T
- A = A ∪{(u,v)} // add the edge to the tree
- UNION(S, T)
- return A
- The performance is:
- Line 1 is O(1)
- Line 2-3 is at least O(V), depending on how we represent sets.
- Line 4 O(E log2E)
- Line 5 is O(E)
- In some discussions we have not had, we can do the set operations in nearly constant time, or O(α(V))
- So the loop is O(E) for all intense and purposes.
- Since the graph is connected, |E| ≤ |V| and |E| ≤ |V|2.
- If we use the latter, log2(|E|) = 2 log2 (|E|)
- So we can state the performance of Kruskal's O(E log2V)
- The main problem here is the union operation.
- This could be O(|S|) where S is the smallest of the two sets.
-
SET-UNION(S,T) wlog: assume |T| ≤ |S|- For each t ∈ T
- S = S ∪ {t}
- In this case, the union is, in the worst case O(n/2),
- But the Union-Find data structure makes this much quicker.
-
MakeSet(x)makes a set containing the element x -
Find(x)- Returns the set of which x is an element
- But also "fixes" the set
-
union(x,y)- Merges the sets x and y
- The idea
- We probably have an array of elements.
- Each element contains
- The element
- A pointer to the element's parent, or null if it is the parent.
- The set id
- is the element's key if the parent is null
- Is the parent's key of the parent is not null
-
MAKE-SET(x)
- x.π = NIL
- x.size = 1
-
Find(x)
- if parent != NIL
- x.key = find(x.π)
- return x.key
-
UNION(x,y)
- a = find(x)
- b = find(y)
- if a.key != b.key
- if (a.size > b.size)
- swap(a,b)
- a.π = b
- b.size += a.size
- Trace this with
- elements a b c d e f g
- Do
a ∪ b c ∪ d d ∪ b d ∪ f f ∪ g g ∪ d
-