I’ve been struggling with the code used to implement Prim’s Algorithm in Python. I really hope that someone help me as I needed this specific code for my Case Study. Thank you!
Here’s the code:
# A Python program for Prims's MST for # adjacency list representation of graph from collections import defaultdict import sys class Heap(): def __init__(self): self.array =  self.size = 0 self.pos =  def newMinHeapNode(self, v, dist): minHeapNode = [v, dist] return minHeapNode # A utility function to swap two nodes of # min heap. Needed for min heapify def swapMinHeapNode(self, a, b): t = self.array[a] self.array[a] = self.array[b] self.array[b] = t # A standard function to heapify at given idx # This function also updates position of nodes # when they are swapped. Position is needed # for decreaseKey() def minHeapify(self, idx): smallest = idx left = 2 * idx + 1 right = 2 * idx + 2 if left < self.size and self.array[left] < \ self.array[smallest]: smallest = left if right < self.size and self.array[right] < \ self.array[smallest]: smallest = right # The nodes to be swapped in min heap # if idx is not smallest if smallest != idx: # Swap positions self.pos[ self.array[smallest] ] = idx self.pos[ self.array[idx] ] = smallest # Swap nodes self.swapMinHeapNode(smallest, idx) self.minHeapify(smallest) # Standard function to extract minimum node from heap def extractMin(self): # Return NULL wif heap is empty if self.isEmpty() == True: return # Store the root node root = self.array # Replace root node with last node lastNode = self.array[self.size - 1] self.array = lastNode # Update position of last node self.pos[lastNode] = 0 self.pos[root] = self.size - 1 # Reduce heap size and heapify root self.size -= 1 self.minHeapify(0) return root def isEmpty(self): return True if self.size == 0 else False def decreaseKey(self, v, dist): # Get the index of v in heap array i = self.pos[v] # Get the node and update its dist value self.array[i] = dist # Travel up while the complete tree is not # hepified. This is a O(Logn) loop while i > 0 and self.array[i] < \ self.array[(i - 1) / 2]: # Swap this node with its parent self.pos[ self.array[i] ] = (i-1)/2 self.pos[ self.array[(i-1)/2] ] = i self.swapMinHeapNode(i, (i - 1)/2 ) # move to parent index i = (i - 1) / 2; # A utility function to check if a given vertex # 'v' is in min heap or not def isInMinHeap(self, v): if self.pos[v] < self.size: return True return False def printArr(parent, n): for i in range(1, n): print ("% d - % d" % (parent[i], i)) class Graph(): def __init__(self, V): self.V = V self.graph = defaultdict(list) # Adds an edge to an undirected graph def addEdge(self, src, dest, weight): # Add an edge from src to dest. A new node is # added to the adjacency list of src. The node # is added at the begining. The first element of # the node has the destination and the second # elements has the weight newNode = [dest, weight] self.graph[src].insert(0, newNode) # Since graph is undirected, add an edge from # dest to src also newNode = [src, weight] self.graph[dest].insert(0, newNode) # The main function that prints the Minimum # Spanning Tree(MST) using the Prim's Algorithm. # It is a O(ELogV) function def PrimMST(self): # Get the number of vertices in graph V = self.V # key values used to pick minimum weight edge in cut key =  # List to store contructed MST parent =  # minHeap represents set E minHeap = Heap() # Initialize min heap with all vertices. Key values of all # vertices (except the 0th vertex) is is initially infinite for v in range(V): parent.append(-1) key.append(sys.maxint) minHeap.array.append( minHeap.newMinHeapNode(v, key[v]) ) minHeap.pos.append(v) # Make key value of 0th vertex as 0 so # that it is extracted first minHeap.pos = 0 key = 0 minHeap.decreaseKey(0, key) # Initially size of min heap is equal to V minHeap.size = V; # In the following loop, min heap contains all nodes # not yet added in the MST. while minHeap.isEmpty() == False: # Extract the vertex with minimum distance value newHeapNode = minHeap.extractMin() u = newHeapNode # Traverse through all adjacent vertices of u # (the extracted vertex) and update their # distance values for pCrawl in self.graph[u]: v = pCrawl # If shortest distance to v is not finalized # yet, and distance to v through u is less than # its previously calculated distance if minHeap.isInMinHeap(v) and pCrawl < key[v]: key[v] = pCrawl parent[v] = u # update distance value in min heap also minHeap.decreaseKey(v, key[v]) printArr(parent, V) def main(): #pass graph = Graph(9) graph.addEdge(0, 7, 8) graph.addEdge(1, 2, 8) graph.addEdge(1, 7, 11) graph.addEdge(2, 3, 7) graph.addEdge(2, 8, 2) graph.addEdge(2, 5, 4) graph.addEdge(3, 4, 9) graph.addEdge(3, 5, 14) graph.addEdge(4, 5, 10) graph.addEdge(5, 6, 2) graph.addEdge(6, 7, 1) graph.addEdge(6, 8, 6) graph.addEdge(7, 8, 7) graph.PrimMST() if __name__ == '__main__': main()
When I tried to run it, it returns an error ‘Graph’ object has no attribute ‘addEdge’. I specifically need this code since this kind of Prim’s Algorithm used a Edge List (node, node, weight) in adding an edge unlike other code that use Adjacency Matrix. Therefore, it is much easier to use this kind of code. Helping me would a huge help for my subject.