Kruskal's Algorithm
Kruskal's Algorithm is an algorithm for building a Minimum Spanning Tree, an alternative to Prim's Algorithm.
- Step 1: Sort all edges in non-decreasing order of their weights
- Step 2: Select the smallest edge that does not form a cycle and add it to the tree
- Step 3: Repeat until all vertices are included
Algorithm
Code
class Graph:
def __init__(self, vertices=None, edges=None):
self.vertices = vertices or set()
self.edges = edges or []
def add_vertex(self, vertex):
self.vertices.add(vertex)
def add_edge(self, from_vertex, to_vertex, weight):
self.edges.append((from_vertex, to_vertex, weight))
def find_parent(self, parent, vertex):
if parent[vertex] == vertex:
return vertex
return self.find_parent(parent, parent[vertex])
def union(self, parent, rank, v1, v2):
root1 = self.find_parent(parent, v1)
root2 = self.find_parent(parent, v2)
if rank[root1] < rank[root2]:
parent[root1] = root2
elif rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root2] = root1
rank[root1] += 1
def kruskals_algorithm(G: Graph):
edges = sorted(G.edges, key=lambda e: e[2])
T = Graph()
parent = {v: v for v in G.vertices}
rank = {v: 0 for v in G.vertices}
for from_v, to_v, weight in edges:
if G.find_parent(parent, from_v) != G.find_parent(parent, to_v):
T.add_vertex(from_v)
T.add_vertex(to_v)
T.add_edge(from_v, to_v, weight)
G.union(parent, rank, from_v, to_v)
return T