7.Prim's Algorithm

PHOTO EMBED

Tue Nov 19 2024 16:38:14 GMT+0000 (Coordinated Universal Time)

Saved by @varuntej #python 

Task-8
Implement Prim's algorithm
Algorithm:
Algorithm Prim(E, cost, n, t)
// E is the set of edges in G. cost[1 : n, 1 : n] is the cost 
//adjacency matrix of an n-vertex graph such that cost[i, j] is 
//either a positive real number or ∞ if no edge (i, j) exists.
// A minimum spanning tree is computed and stored as a set of edges in the array t[1 : n − 1, 1 : 2].
// (t[i, 1], t[i, 2]) is an edge of 
//the minimum-cost spanning tree. The final cost is returned.
{
Let (k, l) be an edge of minimum cost in E;
mincost := cost[k, l];
t[1, 1] := k; t[1, 2] := l;

For i := 1 to n do // Initialize near.

if (cost[i, l] < cost[i, k]) then near[i] := l;  
else near[i] := k;  
near[k] := near[l] := 0;

For i := 2 to n − 1 do
{
// Find n − 2 additional edges for t.  
Let j be an index such that near[j] ≠ 0 and cost[j, near[j]] is minimum;  
t[i, 1] := j; t[i, 2] := near[j];  
mincost := mincost + cost[j, near[j]];  
near[j] := 0;  
for k := 1 to n do  
    if ((near[k] ≠ 0) and (cost[k, near[k]] > cost[k, j]))  
        then near[k] := j;  
}
Return mincost;
}

Program:
#PRIM.PY

class Graph():
  def __init__(self, v):
    self.V = v
    # graph[][] ~~~ cost [][]
    # cost = inf ~~ 1000000007 if no edge between pair
    # initially no edges
    self.cost = [[1000000007 for cols in range(v)] for rows in range(v)]

  def add_edge(self,u,v,w):
    # add edge and override cost
    self.cost[u][v] = self.cost[v][u] = w


  def prim(self):

    # helper functions

    def find_min_edge():
      min_edge = 1000000007 #~~ inf
      # initilize (k,l) to (-1,-1)
      k,l = -1,-1
      for i in range(self.V):
        for j in range(self.V):
          if i!=j and self.cost[i][j]<min_edge:
            min_edge = self.cost[i][j]
            k,l = i,j
      return k,l

    def find_next_edge(near):
      j = -1
      min_cost = 1000000007 # ~inf
      for i in range(self.V):
        if near[i]!=-1 and self.cost[i][near[i]]<min_cost:
          min_cost = self.cost[i][near[i]]
          j = i
      return j

    def update_near(near, j):
      for k in range(self.V):
        if near[k]!=-1 and self.cost[k][near[k]] > self.cost[k][j]:
          near[k] = j

    def cout(t):
      print()
      print("selected edges :")
      for edge in t:
        print(edge[0]+1,edge[1]+1,self.cost[edge[0]][edge[1]])



    # The main function to construct MST using prim's algorithm 



    # t[1:n-1,1:2] : selected edges, exactly n-1
    t = [[0,0] for i in range(self.V-1)]

    # find (k,l) an edge with minimum cost
    k,l = find_min_edge()
    mincost = self.cost[k][l]
    t[0][0], t[0][1] = k,l

    # define near[]
    near = [-1]*self.V

    for i in range(self.V):
      if self.cost[i][l]<self.cost[i][k]:
        near[i] = l
      else:
        near[i] = k
    
    near[k] = near[l] = -1

    for i in range(1,self.V-1):
      # j is the next vertex where near[j]!=0 and cost[j][near[j]] is minimum
      j = find_next_edge(near)
      # add to selected edges
      t[i][0],t[i][1] = j,near[j]
      mincost += self.cost[j][near[j]]
      # set near[j] to 0
      near[j] = -1

      # update near
      update_near(near,j)

    # print selected edges and mincost
    
    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.prim()

  '''

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
5 6 25
4 5 22
3 4 12
2 3 16
7 2 14
mincost :  99

'''
content_copyCOPY