8. Kruskal's Algorithm

PHOTO EMBED

Tue Nov 19 2024 16:39:06 GMT+0000 (Coordinated Universal Time)

Saved by @varuntej #python 

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

'''
content_copyCOPY