standard04.md

STD 04 - Implement Prim’s Algorithm

Intro

Prim's Algorithm is a greedy algorithm that finds the minimum spanning tree of a connected weighted graph. It starts with a single vertex and iteratively adds the minimum weight edge that connects a vertex in the tree to a vertex outside the tree until all vertices are included in the tree.

Task

Using the python code, complete the code to produce the following output for the given graph:

Edge 	 Weight
0 - 1 	 2
1 - 2 	 3
0 - 3 	 6
1 - 4 	 5

Note that this is an advanced algorithm, so to simplify the task for standard level, we have provided full comments throughout to aid understanding. This means that if you select this task as one of the 3 standard tasks to write up, you need to provide no further comments (altho’ you might provide docstrings). You will of course need to give an explanation as well as critical comment.

Python code

import sys                                                      #needed for maxsize
  
class Graph(): 
  
    def __init__(self, vertices):                               #implements graph as adjacency matrix
        self.V = vertices                                       #number of vertices
        self.graph = [[0 for column in range(vertices)]         #adjacency matrix with no edges (all connections set to zero)
                    for row in range(vertices)] 
  
    def printMST(self, parent): 
        print ("Edge \t Weight")
        for i in range(1, self.V): 
            print (parent[i], "-", i, "\t", self.graph[i][ parent[i] ])
  
                                                                #from reached nodes find the unreached node with the minimum cost
    def minKey(self, key, mstSet): 
        min = sys.maxsize                                       #set min to infinity (use maxsize which is next best thing!)
        for v in range(self.V):                                 #count through number of vertices
            if key[v] < min and mstSet[v] == False:             #if vertex is less than min and unreached
                min = key[v]                                    #assign to min 
                min_index = v                                   #min_index is position of min in key
        return min_index                                        #return min_index
  
                                                                #find MST 
    def primMST(self): 
        key = [sys.maxsize] * self.V                            #initialise key to list of values all set to infinity; same length as self.V              
        parent = [None] * self.V                                #list for constructed MST 
        key[0] = 0                                              #set first element of key to zero (this is where we start)                                                                                   
        mstSet = [False] * self.V                               #mstSet is list of booleans set to False
        parent[0] = -1                                          #first element of parent list set to -1                        
  
        for vertex in range(self.V):                            #go through all vertices
            u = self.minKey(key, mstSet)                        #call minKey; minKey returns u (index of unreached node) 
            mstSet[u] = True                                    #mstSet at index of node is set to True                                                                                                
            for v in range(self.V):                             #go through all vertices
                
                                                                #if edge from u to connected node v is > 0 (if there is an edge)
            ### COMPLETE CODE HERE; FULL COMMENTS TO            #and mstSet[v] is unreached 
            ### THE RIGHT                                       #and key[v] is greater than the edge cost
                                                                #(only if the current edge cost is greater will need to change)
                                                                #key[v] takes edge cost



                    parent[v] = u                               #parent[v] is index of node; so list of parents (nodes) is the MST
  
        self.printMST(parent)                                   #print the list of parents, i.e. the MST                                
  
g = Graph(5) 
g.graph = [ [0, 2, 0, 6, 0], 
            [2, 0, 3, 8, 5], 
            [0, 3, 0, 0, 7], 
            [6, 8, 0, 0, 9], 
            [0, 5, 7, 9, 0]] 
  
g.primMST();