Prim's Algorithm MST implementation in Python

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

Coders Packet

Prim's Algorithm MST implementation in Python

Comments