# Kruskal's Minimum Spanning Tree Algorithm

Kruskal's MST Algorithm by Lalitha Natraj
ðŸ”—
Kruskal's MST Algorithm by William Fiset
ðŸ”—

Kruskal’s algorithm is a graph based algorithm which is used to build Minimum Spanning Tree (MST) for a given weighted, undirected graph. It creates MST by greedily adding the cheapest available edge to the tree, as long as it does not create a cycle. The algorithm starts by sorting all the edges in the graph in ascending order of their weights. Then, it iterates through the sorted edges and adds each edge to the MST if it does not create a cycle. The algorithm continues until all the vertices are connected, forming the MST.

## What is a Minimum Spanning Tree?

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all the vertices together with the minimum possible total edge weight. In other words, it is the cheapest or minimum cost subgraph in a given graph that connects all the nodes in the graph.

For example, for the undirected weighted graph shown below:

Below is how the minimum spanning tree looks like:

## Detailed Steps of Kruskal’s MST Algorithm

Below are the steps involved in Kruskal’s algorithm to find Minimum Spanning Tree (MST) of an undirected and weighted graph:

Preliminary Step: Representation of Graph

• Represent the graph as a list of edges, where each edge is a tuple `(u, v, w)` representing a connection between vertices `u` and `v` with weight `w`.

Step 1: Edge Sorting

• Sort all edges in the graph in ascending order based on their weights.

Step 2: Initialization of Data Structure For Detecting Cycles

Step 3: Edge Selection and Component Merging

• Iterate through the sorted edges:
• For each edge `(u, v, w)`, determine if vertices `u` and `v` belong to different components.
• If they are in different components:
• Add this edge to the minimum spanning tree.
• Merge the components containing `u` and `v` in the disjoint set data structure.
• If they are in the same component, discard this edge to avoid creating a cycle.

Step 4: Termination

• Continue Step 3 until either:
• All vertices are in the same component (indicating a fully connected MST), or
• All edges have been processed.

The final result is the minimum spanning tree, which is a subgraph of the original graph that connects all vertices with the minimum total weight of the edges.

## Implementation of Kruskal’s Algorithm

``````
# Function to find the root of a node in the disjoint set
def find_root(parent, node):
# If the node is not the root, recursively find the root
if parent[node] != node:
parent[node] = find_root(parent, parent[node])
return parent[node]

# Function to union two nodes in the disjoint set
def union_components(parent, node1, node2):
# Find the roots of the two nodes
root1 = find_root(parent, node1)
root2 = find_root(parent, node2)

# Merge/Union both components
# By setting the parent of one root to the other root
parent[root1] = root2

# Function to implement Kruskal's MST algorithm
def kruskals_mst(edges, nodes):
# Initialize the parent info for each node used for disjoint set
parent = {node:node for node in nodes}

# Sort the edges by weight in ascending order
edges.sort(key=lambda x: x[2])

# Initialize an array to store all edges in the MST
mst = []
total_weight = 0

# Iterate through the sorted edges
for node1, node2, weight in edges:
# If the two nodes are not in the same set/component, add the edge to the MST
if find_root(parent, node1) != find_root(parent, node2):
mst.append((node1, node2, weight))
total_weight += weight
union_components(parent, node1, node2)

return mst, total_weight

if __name__ == "__main__":
# Example graph represented as edges: (node1, node2, weight)
edges = [("A", "B", 8), ("A", "D", 2), ("A", "E", 4), ("B", "C", 7), ("B", "F", 4), ("C", "D", 9), ("C", "F", 6), ("D", "E", 5), ("E", "F", 3)]
nodes = ["A","B","C","D","E","F"]

mst, total_weight = kruskals_mst(edges, nodes)

print("Minimum Spanning Tree edges:")
for edge in mst:
print(f"({edge[0]} - {edge[1]}) with weight {edge[2]}")
print(f"Total weight of MST: {total_weight}")
``````

## Time & Space Complexity

### Time Complexity

The time complexity of Kruskal’s algorithm for finding Minimum Spanning Tree in a graph is `O(E log E)`, where `E` is the number of edges present in the graph.

The reason for this time complexity is as follows:

• Sorting the edges: The first step of Kruskal’s algorithm is to sort the edges in ascending order of their weights. This step takes `O(E log E)` time.
• Checking for cycles: As the algorithm progresses, it checks whether adding an edge to the MST would create a cycle. This is done using a data structure called a disjoint-set (or union-find) data structure, which allows for efficient checking of whether two vertices are in the same connected component. Efficient implementations of disjoint-set data structure brings the overall time complexity of this step to `O(E)`.
• Adding edges to the MST: The final step is to add the edges to the MST. This can be done in `O(1)` time per edge, as it involves appending the edge to the end of MST array.

Combining these steps, the overall time complexity of Kruskal’s algorithm is `O(E log E)`.

### Space Complexity

The space complexity of Kruskal’s algorithm is `O(V + E)`, where `V` is the number of vertices and `E` is the number of edges in the graph.

The reason for this space complexity is as follows:

• Storing the graph: The algorithm needs to sort and store all edges in the graph, which requires `O(E)` space.
• Storing the disjoint-set data structure: The algorithm uses a disjoint-set data structure to keep track of the connected components in the graph. This data structure requires `O(V)` space to store the parent information for each vertex.

Combining these space requirements, the overall space complexity of Kruskal’s algorithm is `O(V + E)`.