Minimum Spanning Trees Kruskal’s Algorithm
Kruskal’s Algorithm
There are two MST algorithms based on the same greedy choice
Kruskal’s Algorithm (Input: a connected, weighted graph G = (V ,E ))
Sort all edges in G by weight
Put each vertex in G into a separate set
For (u, v) ∈ E (in order)
If u and v are in different sets
Add (u, v) to the MST
Combine u’s set with v ’s set
Gradually join |V | components
Add next lowest weight edge if it joins two components
Algorithms (580) Weighted Graphs February 2018 21 / 54
Minimum Spanning Trees Kruskal’s Algorithm
Kruskal’s Algorithm
The set of edges is iterated over in weight order
If the next edge connects two distinct components it is added
Algorithms (580) Weighted Graphs February 2018 22 / 54
Minimum Spanning Trees Kruskal Implementation
Implementing Kruskal’s Algorithm
Kruskal’s Algorithm (Input: a connected, weighted graph G = (V ,E ))
Sort all edges in G by weight
Put each vertex in G into a separate set
For (u, v) ∈ E (in order)
If u and v are in different sets
Add (u, v) to the MST
Combine u’s set with v ’s set
Question
How can the basic algorithm be implemented?
What is returned?
What data structures could be used?
What would be the performance?
Algorithms (580) Weighted Graphs February 2018 23 / 54
Minimum Spanning Trees Kruskal Implementation
Kruskal’s Algorithm: Implementation
Kruskal’s Algorithm (Input: a connected, weighted graph G = (V ,E ))
1 T = new Graph(V)
2 Add all edges in E to a queue Q prioritised by min weight
3 for v in V
4 Set Sv = {v}
5 while Q is not empty
6 {x,y} = Q.remove()
7 if x in Si and y in Sj and i != j
8 T.add edge(x,y)
9 Si = Si + Sj
10 Sj = {}
11 return T
T is a new graph, initialise with V (line 1), then add edges (line 8)
Sorting or using priority queue are equivalent
Algorithms (580) Weighted Graphs February 2018 24 / 54
Minimum Spanning Trees Kruskal Performance
Kruskal’s Algorithm: Performance
Kruskal’s Algorithm (Input: a connected, weighted graph G = (V ,E ))
1 T = new Graph(V)
2 Add all edges in E to a queue Q prioritised by min weight
3 for v in V
4 Set Sv = {v}
5 while Q is not empty
6 {x,y} = Q.remove()
7 if x in Si and y in Sj and i != j
8 T.add edge(x,y)
9 Si = Si + Sj
10 Sj = {}
11 return T
Question
What is the time complexity?
Algorithms (580) Weighted Graphs February 2018 25 / 54
Minimum Spanning Trees Kruskal Performance
Kruskal’s Algorithm: Performance
Kruskal’s Algorithm (Input: a connected, weighted graph G = (V ,E ))
1 T = new Graph(V)
2 Add all edges in E to a queue Q prioritised by min weight
3 for v in V
4 Set Sv = {v} // use “disjoint sets” structure
5 while Q is not empty
6 {x,y} = Q.remove()
7 if x in Si and y in Sj and i != j
8 T.add edge(x,y)
9 Si = Si + Sj
10 Sj = {}
11 return T
The disjoint set data structure is O(log |V |) for all operations
See books for details
Algorithms (580) Weighted Graphs February 2018 26 / 54
Minimum Spanning Trees Kruskal Performance
Performance of Kruskal’s Algorithm
For a graph with V vertices and E edges:
Sorting the edges is O(E log2 E )
Remainder depends on set operations
Operations on disjoint sets such as these possible in O(logV ) time
See disjoint set (Cormen) , union-find (Sedgewick) data structure
So, the loop to build the MST is O(E log2 V )
E < V 2, so log2 E < 2 log2 V and E log2 E = O(E log2 V ) So, overall time is O(E log2 V ) Algorithms (580) Weighted Graphs February 2018 27 / 54 Minimum Spanning Trees Prim’s Algorithm Prim’s Algorithm Prim’s Algorithm (Input: connected, weighted graph G = (V ,E ), vertex r) Add r to MST While MST has fewer than |V | − 1 edges Add least weight edge that connects MST to new vertex Focus on one component Only consider edges from that component Algorithms (580) Weighted Graphs February 2018 28 / 54 Minimum Spanning Trees Prim Implementation Prim’s Algorithm: Implementation Prim’s Algorithm (Input: connected, weighted graph G , vertex r) T = new Graph(G.num vertices) tree vertex = new boolean[G.num vertices] tree vertex[r] = true Q = new MinPriorityQueue() // by weight for v in G.adj[r] { Q.add((r,v)) } while T has fewer than |V| - 1 edges (x,y) = Q.remove() // tree vertex[x] is true if not tree vertex[y] tree vertex[y] = true T.add edge(x,y) for v in G.adj[y] { Q.add((y,v)) } return T Just one set of vertices to track No new data structures needed Algorithms (580) Weighted Graphs February 2018 29 / 54 Minimum Spanning Trees Prim Performance Prim’s Algorithm Discussion What is the time complexity of Prim’s algorithm? Prim’s Algorithm (Input: connected, weighted graph G , vertex r) T = new Graph(G.num vertices) tree vertex = new boolean[G.num vertices] tree vertex[r] = true Q = new MinPriorityQueue() // by weight for v in G.adj[r] { Q.add((r,v)) } while T has fewer than |V| - 1 edges (x,y) = Q.remove() // tree vertex[x] is true if not tree vertex[y] tree vertex[y] = true T.add edge(x,y) for v in G.adj[y] { Q.add((y,v)) } return T Algorithms (580) Weighted Graphs February 2018 30 / 54 Minimum Spanning Trees Prim Performance Performance of Prim’s Algorithm Prim’s Algorithm also executes in O(E log2 V ) time assuming a queue implemented as a binary heap The queue operations determine the running time All edges are added to the queue Worst case: all edges removed from queue E log2 E = O(E log2 V ) as before Algorithms (580) Weighted Graphs February 2018 31 / 54