Coders Packet

Prim's Algorithm MST implementation in Python

By PRIYA KUMARI

  • prims/
  • Given module calculates the minimum spanning tree for a graph using Prim's algorithm. This algorithm is implemented using heapq module.

    -->Description of Graph class :- The graph class of creates an adjacency list.

    Description of addEdge(self,u,v,w):- This method stores the new vertices and edges, where u and v are the starting and ending vertices and w is the weight of the edges between these vertices.

    Description of method prims(g) :- This method takes argument as g which is our graph, and then uses the prims algorithm to find the minimum spanning tree for the graph.

    This algorithm is implemented using heap. The time complexity of this algorithm is O(v log e), where v is the number of vertices and e is the number of edges.

    -->How to use the packet.

    Import the prims module to your program

    1) Enter the value of u,v, and w

    2) Pass the value of u,v and w into the method addEdge and call the prims method, it will find the minimum spanning tree of the graph class.

    Code

    from heapq import *
    import sys

    class Graph:
        """ graph class """
        def __init__(self,v):
            self.v=v
            self.adjList={i:[] for i in range(1,v+1)}

        def __str__(self):
            g='''Graph(\n'''
            for i in self.adjList:
                g+=f" {i}: {self.adjList[i]}\n"
            g+=")"
            return g

        def addEdge(self,u,v,w):
            self.adjList[u].append((v,w))
            self.adjList[v].append((u,w))


    def prims(g):
        active_edges=[]
       
        mst={i:False for i in g.adjList}
        cost=0
        heappush(active_edges,[0,1])
       
        while len(active_edges)!=0:
            wt,node=heappop(active_edges)

            if mst[node]:
                continue

            mst[node]=True
            cost+=wt

            for v,w in g.adjList[node]:
                if not mst[v]:
                    heappush(active_edges,[w,v])
        return cost

    Output

     

    Download Complete Code

    Comments

    Comments for the packet "Prim's Algorithm MST implementation in Python";
    No comments yet