Scribd
Upload
5 views2 pages

Greedy Algorithm: Kruskal's MST Code

The document describes the implementation of the Greedy Search Algorithm, specifically Kruskal's algorithm for finding the Minimum Spanning Tree (MST) of a graph. It includes functions for finding the root of a vertex, performing union operations, and constructing the MST from given vertices and edges. An example input and output demonstrate how to use the algorithm to calculate the MST and its total cost.

Uploaded by

riddhitaharabadkar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Greedy Algorithm: Kruskal's MST Code

The document describes the implementation of the Greedy Search Algorithm, specifically Kruskal's algorithm for finding the Minimum Spanning Tree (MST) of a graph. It includes functions for finding the root of a vertex, performing union operations, and constructing the MST from given vertices and edges. An example input and output demonstrate how to use the algorithm to calculate the MST and its total cost.

Uploaded by

riddhitaharabadkar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

3.

Greedy Search Algorithm

#Greedy Search Algorithm


def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])

def union(parent, rank, x, y):


xroot = find(parent, x)
yroot = 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 kruskal(vertices, edges):


parent = [i for i in range(vertices)]
rank = [0] * vertices
mst = []

[Link](key=lambda x: x[2]) # Sort edges by weight


for u, v, weight in edges:
if find(parent, u) != find(parent, v):
[Link]((u, v, weight))
union(parent, rank, u, v)
return mst

vertices = int(input("Enter the number of vertices: "))


edges_count = int(input("Enter the number of edges: "))
edges = []
for _ in range(edges_count):
u, v, weight = map(int, input("Enter edge (u v weight): ").split())
[Link]((u, v, weight))

mst = kruskal(vertices, edges)

print("Minimum Spanning Tree (MST):")


total_cost = 0
for u, v, weight in mst:
print(f"Edge ({u}, {v}) with weight {weight}")
total_cost += weight
print(f"Total cost of MST: {total_cost}")

OUTPUT:

Enter the number of vertices: 4


Enter the number of edges: 5
Enter edge (u v weight): 0 1 10
Enter edge (u v weight): 0 2 6
Enter edge (u v weight): 0 3 5
Enter edge (u v weight): 1 3 15
Enter edge (u v weight): 2 3 4

Minimum Spanning Tree (MST):


Edge (2, 3) with weight 4
Edge (0, 3) with weight 5
Edge (0, 1) with weight 10
Total cost of MST: 19

You might also like