Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a connected, undirected graph. It works by sorting the edges by weight and building the MST by adding edges one by one if they do not form a cycle. A union-find data structure is used to check if adding an edge would create a cycle by determining if its endpoints are in the same component tree. The algorithm runs in O(E log E) time using an efficient union-find implementation. The correctness of Kruskal's algorithm is proven by showing that the graph produced after each step is a subgraph of some MST.
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a connected, undirected graph. It works by sorting the edges by weight and building the MST by adding edges one by one if they do not form a cycle. A union-find data structure is used to check if adding an edge would create a cycle by determining if its endpoints are in the same component tree. The algorithm runs in O(E log E) time using an efficient union-find implementation. The correctness of Kruskal's algorithm is proven by showing that the graph produced after each step is a subgraph of some MST.
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a connected, undirected graph. It works by sorting the edges by weight and building the MST by adding edges one by one if they do not form a cycle. A union-find data structure is used to check if adding an edge would create a cycle by determining if its endpoints are in the same component tree. The algorithm runs in O(E log E) time using an efficient union-find implementation. The correctness of Kruskal's algorithm is proven by showing that the graph produced after each step is a subgraph of some MST.
Kruskal's algorithm is a greedy algorithm that finds a minimum spanning tree (MST) for a connected, undirected graph. It works by sorting the edges by weight and building the MST by adding edges one by one if they do not form a cycle. A union-find data structure is used to check if adding an edge would create a cycle by determining if its endpoints are in the same component tree. The algorithm runs in O(E log E) time using an efficient union-find implementation. The correctness of Kruskal's algorithm is proven by showing that the graph produced after each step is a subgraph of some MST.
Copyright:
Attribution Non-Commercial (BY-NC)
Available Formats
Download as PDF, TXT or read online from Scribd
Download as pdf or txt
You are on page 1/ 15
Lecture 11: Kruskals MST Algorithm
CLRS Chapter 23 Main Topics of This Lecture
Kruskals algorithm Another, but different, greedy MST algorithm
Introduction to UNION-FIND data structure. Used in Kruskals algorithm Will see implementation in next lecture.
Idea of Kruskals Algorithm Build a forest. Initially, trees of the forest are the vertices (no edges). In each step add the cheapest edge that does not create a cycle. Continue until the forest is a single tree. (Why is a single tree created?) This is a minimum spanning tree (we must prove this).
Step 1: Choose an edge e in F of minimum weight, and check whether adding e to A creates a cycle. If yes, remove e from F . If no, move e from F to A.
Step 2: If F = , stop and output the minimal spanning tree (V, A). Otherwise go to Step 1.
Remark: Will see later, after each step, (V, A) is a subgraph of a MST.
Outline of Kruskals Algorithm Implementation Questions:
How does algorithm choose edge e F with minimum weight?
How does algorithm check whether adding e to A creates a cycle?
How to Choose the Edge of Least Weight Question: How does algorithm choose edge e F with minimum weight? Answer: Start by sorting edges in E in order of increasing weight. Walk through the edges in this order. (Once edge e causes a cycle it will always cause a cycle so it can be thrown away.)
How to Check for Cycles Observation: At each step of the outlined algorithm, (V, A) is acyclic so it is a forest. If u and v are in the same tree, then adding edge {u, v} to A creates a cycle. If u and v are not in the same tree, then adding edge {u, v} to A does not create a cycle.
Question: How to test whether u and v are in the same tree? High-Level Answer: Use a disjoint-set data structure Vertices in a tree are considered to be in same set. Test if Find-Set(u) = Find-Set(v)? Low -Level Answer: The UNION-FIND data structure implements this: 7
The UNION-FIND Data Structure UNION-FIND supports three operations on collections of disjoint sets: Let n be the size of the universe.
Create-Set(u): O(1) Create a set containing the single element u.
Find-Set(u): O(log n) Find the set containing the element u.
Union(u, v): O(log n) Merge the sets respectively containing u and v into a common set.
For now we treat UNION-FIND as a black box. Will see implementation in next lecture. 8
Kruskals Algorithm: the Details Sort E in increasing order by weight w; O(|E| log |E|)
/* After sorting E = {u1, v1 }, {u2, v2 }, . . . , {u|E|, v|E| } */
A = { }; for (each u in V ) CREATE-SET(u); for i from 1 to |E| do if (FIND-SET(ui) != FIND-SET(vi) ) { add {ui, vi} to A; UNION(ui, vi); } return(A);
O(|V |) O(|E| log |E|)
Remark: With a proper implementation of UNION-FIND, Kruskals algorithm has running time O(|E| log |E|).
Correctness of Kruskals Algorithm Lemma: Let (V, A) be a subgraph (part) of a MST of G = (V, E), and let e = {u, v} E \ A be an edge such that (1) (V, A {e}) has no cycle; (2) e has minimum weight among all edges in E \ A such that (1) is satised. Then (V, A {e}) is a subgraph of some MST containing (V, A).
Corollary: Kruskals algorithm produces a MST.
10
Proof of the Lemma: The Idea
Idea of Proof: Let T be any MST with (V, A) as a subgraph. Then we prove that
either e T so (V, A{e}) is a subgraph of MST T and lemma is correct or
if e T there is edge e T A such that W (e) = W (e ) and T = T {e} {e } is a tree. Since W (T ) = W (T ) this implies T is a MST so (V, A{e}) is a subgraph of MST T so lemma is correct.
11
Proof of the Lemma: The idea
Graph G 1 2 24 2 v v 27
T u {u,v} u u
path in T: u u v
u v v
(V, A u {u,v} ) Case 1 {u,v} in T
(V, A u {u,v} ) Case 2 {u,v} not in T
12
Correctness of Kruskals Algorithm Continued Proof: Let T be any MST with (V, A) as a subgraph. If e T , we are done. Suppose that e = {u, v} T . There is a unique path from u to v in the MST T , which contains at least one edge e E \ A. e = e (because e T but e T ). (V, A {e }) has no cycles (because (V, A {e }) is included in T .) W (e) W (e ) (because both edges in E \ A and assumption (2) in previous page). Consider the new tree T = (T {e}) \ {e }. If W (e) = W (e ), then T is another minimum spanning tree containing (V, A {e}). If W (e) < W (e ), then W (T ) W (T ) = W (e) W (e ) < 0. Contradiction. 13
