Task-9
Implement Kruskal algorithm
Algorithm:
Algorithm Kruskal(E, cost, n, t)
// E is the set of edges in G. G has n vertices. cost[u, v] is the
// cost of edge (u, v). t is the set of edges in the minimum-
// spanning tree. The final cost is returned.
{
Construct a heap out of the edge costs using Heapify;
for i := 1 to n do parent[i] := −1;
// Each vertex is in a different set.
i := 0; mincost := 0.0;
while ((i < n − 1) and (heap not empty)) do
{
Delete a minimum cost edge (u, v) from the heap
and reheapify using Adjust;
j := Find(u); k := Find(v);
if (j ≠ k) then
{
i := i + 1;
t[i, 1] := u; t[i, 2] := v;
mincost := mincost + cost[u, v];
Union(j, k);
}
}
if (i ≠ n − 1) then write ("No spanning tree");
else return mincost;
}
Program:
# KRUSKAL.PY
import heapq
class Graph():
def __init__(self, v):
self.V = v
# graph contains list of edges ** (u, v, w)
# u -> src, v -> destination, w -> weight/cost
self.edges = []
def add_edge(self,u,v,w):
# add edge and override cost
self.edges.append([u,v,w])
def kruskal(self):
# helper functions
def find(parent, i):
if parent[i]==i:
return i
# path compression technique
return find(parent, parent[i])
def union(parent, rank, x, y):
# union by rank
# finding roots of disjoint sets x and y
x_root = find(parent,x)
y_root = find(parent,y)
# Attach smaller rank tree under root of
# high rank tree (Union by Rank)
if rank[x_root]<rank[y_root]:
parent[x_root] = y_root
elif rank[x_root]>rank[y_root]:
parent[y_root] = x_root
else:
# If ranks are same, then make one as root
# and increment its rank by one
parent[y_root] = x_root
rank[x_root] += 1
def cout(t):
print()
print("Selected Edges:")
for edge in t:
print(edge[0]+1,edge[1]+1,edge[2])
# The main function to construct MST using Kruskal's algorithm
# t[1:n-1,1:3] : selected edges, exactly n-1
t = [[0,0,0] for i in range(self.V-1)]
# Create a min-heap of edges
min_heap = []
for u, v, w in self.edges:
heapq.heappush(min_heap, (w, u, v))
parent = [i for i in range(self.V)]
rank = [0]*self.V
# count of edges in t / MST
i = 0
mincost = 0
while i<self.V-1 and min_heap:
w,u,v = heapq.heappop(min_heap)
j = find(parent,u)
k = find(parent,v)
if j!=k:
t[i][0],t[i][1],t[i][2] = u,v,w
i+=1
mincost += w
union(parent,rank,j,k)
cout(t)
print("mincost : ",mincost)
if __name__ == '__main__':
v = int(input("Enter number of vertices :"))
g = Graph(v)
e = int(input("Enter number of Edges :"))
for _ in range(e):
u,v,w = map(int, input().split())
g.add_edge(u-1,v-1,w)
g.kruskal()
'''
INPUT:
7
9
1 6 10
6 5 25
5 4 22
5 7 24
4 3 12
4 7 18
7 2 14
2 3 16
2 1 28
OUTPUT:
Selected Edges:
1 6 10
4 3 12
7 2 14
2 3 16
5 4 22
6 5 25
mincost : 99
'''
