DSAKruskal's Algorithm

Kruskal's Algorithm

Kruskal's algorithm finds the Minimum Spanning Tree (MST), or Minimum Spanning Forest, in an undirected graph.

The MST (or MSTs) found by Kruskal's algorithm is the collection of edges that connect all vertices (or as many as possible) with the minimum total edge weight.

Kruskal's algorithm adds edges to the MST (or Minimum Spanning Forest), starting with the edges with the lowest edge weights.

Edges that would create a cycle are not added to the MST. These are the red blinking lines in the animation above.

Kruskal's algorithm checks all edges in the graph, but the animation above is made to stop when the MST or Minimum Spanning forest is completed, so that you don't have to wait for the longest edges to be checked.

To find out if an edge will create a cycle, we will useUnion-Find cycle detection inside Kruskal's algorithm.

Manual Run Through

Let's run through Kruskal's algorithm manually on the graph below, so that we understand the detailed step-by-step operations before we try to program it.

The first three edges are added to the MST. These three edges have the lowest edge weights and do not create any cycles:

• C-E, weight 2
• D-E, weight 3
• A-B, weight 4

After that, edge C-D (indicated in red) cannot be added as it would lead to a cycle.

The next four edges Kruskal's algorithm tries to add to the MST are:

• E-G, weight 6
• C-G, weight 7 (not added)
• D-F, weight 7
• B-C, weight 8

Edge C-G (indicated in red) cannot be added to the MST because it would create a cycle.

As you can see, the MST is already created at this point, but Kruskal's algorithm will continue to run until all edges are tested to see if they can be added to the MST.

The last three edges Kruskal's algorithm tries to add to the MST are the ones with the highest edge weights:

• A-C, weight 9 (not added)
• A-G, weight 10 (not added)
• F-G, weight 11 (not added)

Each of these edges would create a cycle in the MST, so they cannot be added.

Kruskal's algorithm is now finished.

Run the simulation below to see Kruskal's algorithm doing the manual steps that we have just done.

Implementation of Kruskal's Algorithm

For Kruskal's algorithm to find a Minimum Spanning Tree (MST), or a Minimum Spanning Forest, we create aGraph class. We will use the methods inside thisGraph class later to create the graph from the example above, and to run Kruskal's algorithm on it.

class Graph:    def __init__(self, size):        self.size = size        self.edges = []  # For storing edges as (weight, u, v)        self.vertex_data = [''] * size  # Store vertex names    def add_edge(self, u, v, weight):        if 0<= u< self.size and 0<= v< self.size:            self.edges.append((weight, u, v))  # Add edge with weight                def add_vertex_data(self, vertex, data):        if 0<= vertex< self.size:            self.vertex_data[vertex] = data

Line 8 and 12:Checks if the input argumentsu,v, andvertex, are within the possible range of index values.

To do Union-Find cycle detection in Kruskal's algorithm, these two methodsfind andunion are also defined inside theGraph class:

    def find(self, parent, i):        if parent[i] == i:            return i        return self.find(parent, parent[i])    def union(self, parent, rank, x, y):        xroot = self.find(parent, x)        yroot = self.find(parent, y)        if rank[xroot]< rank[yroot]:            parent[xroot] = yroot        elif rank[xroot] > rank[yroot]:            parent[yroot] = xroot        else:            parent[yroot] = xroot            rank[xroot] += 1

Line 15-18:Thefind method uses theparent array to recursively find the root of a vertex. For each vertex, theparent array holds a pointer (index) to the parent of that vertex. The root vertex is found when thefind method comes to a vertex in theparent array that points to itself. Keep reading to see how thefind method and theparent array are used inside thekruskals_algorithm method.

Line 20-29:When an edge is added to the MST, theunion method uses theparent array to merge (union) two trees. Therank array holds a rough estimate of the tree height for every root vertex. When merging two trees, the root with a lesser rank becomes a child of the other tree's root vertex.

Here is how Kruskal's algorithm is implemented as a method inside theGraph class:

    def kruskals_algorithm(self):        result = []  # MST        i = 0 # edge counter        self.edges = sorted(self.edges, key=lambda item: item[2])        parent, rank = [], []        for node in range(self.size):            parent.append(node)            rank.append(0)        while i< len(self.edges):            u, v, weight = self.edges[i]            i += 1            x = self.find(parent, u)            y = self.find(parent, v)            if x != y:                result.append((u, v, weight))                self.union(parent, rank, x, y)        print("Edge \tWeight")        for u, v, weight in result:            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")

Line 35:The edges must be sorted before Kruskal's algorithm starts trying to add the edges to the MST.

Line 40-41:Theparent andrank arrays are initialized. To start with, every vertex is its own root (every element in theparent array points to itself), and every vertex has no height (0 values in therank array).

Line 44-45:Pick the smallest edge, and incrementi so that the correct edge is picked in the next iteration.

Line 47-51:If the verticesu andv at each end of the current edge have different rootsx andy, it means there will be no cycle for the new edge and the trees are merged. To merge the trees, the current edge is added to theresult array, and we run theunion method to make sure the trees are merged correctly, so that there is only one root vertex in the resulting merged tree.

Now let's create the graph from the "Manual Run Through" above and run Kruskal's algorithm on it:

class Graph:    def __init__(self, size):        self.size = size        self.edges = []  # For storing edges as (weight, u, v)        self.vertex_data = [''] * size  # Store vertex names    def add_edge(self, u, v, weight):        if 0<= u< self.size and 0<= v< self.size:            self.edges.append((u, v, weight))  # Add edge with weight                def add_vertex_data(self, vertex, data):        if 0<= vertex< self.size:            self.vertex_data[vertex] = data    def find(self, parent, i):        if parent[i] == i:            return i        return self.find(parent, parent[i])    def union(self, parent, rank, x, y):        xroot = self.find(parent, x)        yroot = self.find(parent, y)        if rank[xroot]< rank[yroot]:            parent[xroot] = yroot        elif rank[xroot] > rank[yroot]:            parent[yroot] = xroot        else:            parent[yroot] = xroot            rank[xroot] += 1    def kruskals_algorithm(self):        result = []  # MST        i = 0  # edge counter        self.edges = sorted(self.edges, key=lambda item: item[2])        parent, rank = [], []        for node in range(self.size):            parent.append(node)            rank.append(0)        while i< len(self.edges):            u, v, weight = self.edges[i]            i += 1                        x = self.find(parent, u)            y = self.find(parent, v)            if x != y:                result.append((u, v, weight))                self.union(parent, rank, x, y)        print("Edge \tWeight")        for u, v, weight in result:            print(f"{self.vertex_data[u]}-{self.vertex_data[v]} \t{weight}")g = Graph(7)g.add_vertex_data(0, 'A')g.add_vertex_data(1, 'B')g.add_vertex_data(2, 'C')g.add_vertex_data(3, 'D')g.add_vertex_data(4, 'E')g.add_vertex_data(5, 'F')g.add_vertex_data(6, 'G')g.add_edge(0, 1, 4)  #A-B,  4g.add_edge(0, 6, 10) #A-G, 10g.add_edge(0, 2, 9)  #A-C,  9g.add_edge(1, 2, 8)  #B-C,  8g.add_edge(2, 3, 5)  #C-D,  5g.add_edge(2, 4, 2)  #C-E,  2g.add_edge(2, 6, 7)  #C-G,  7g.add_edge(3, 4, 3)  #D-E,  3g.add_edge(3, 5, 7)  #D-F,  7g.add_edge(4, 6, 6)  #E-G,  6g.add_edge(5, 6, 11) #F-G, 11print("Kruskal's Algorithm MST:")g.kruskals_algorithm()

Time Complexity for Kruskal's Algorithm

For a general explanation of what time complexity is, visitthis page.

With \(E\) as the number of edges in our graph, the time complexity for Kruskal's algorithm is

\[ O( E \cdot log{E} ) \]

We get this time complexity because the edges must be sorted before Kruskal's can start adding edges to the MST. Using a fast algorithm likeQuick Sort orMerge Sort gives us a time complexity of \( O( E \cdot log{E} ) \) for this sorting alone.

After the edges are sorted, they are all checked one by one, to see if they will create a cycle, and if not, they are added to the MST.

Although it looks like a lot of work to check if a cycle will be created using thefind method, and then to include an edge to the MST using theunion method, this can still be viewed as one operation. The reason we can see this as just one operation is that it takes approximately constant time. That means that the time this operation takes grows very little as the graph grows, and so it does actually not contribute to the overall time complexity.

Since the time complexity for Kruskal's algorithm only varies with the number of edges \(E\), it is especially fast for sparse graphs where the ratio between the number of edges \(E\) and the number of vertices \(V\) is relatively low.