in python and not the Brute Force approach:

MST implementation: a. Implement Prims' algorithm Name your function Prims(G). Include function in the file MST.PY. Mention in your submission the input format and output format of your program.

pseudocode:

def prims(G): s -> for v in V: #v: current vertex; V: all the vertices in G dist[v] = infinity prev[v] = Empty #initalize source dist[v] = 0 prev[v] = s #update neighbouring nodes of s for node in s.neighbours dist[v] = w(s,node) prev[v] = s while(len(visited) CurrentNode = unvisited vertex v with smallest dist[v] MST.add((prevNode, CurrentNode)) for node in CurrentNode.neighbours: dist[node] = min(w(CurrentNode, node), dist[node]) if dist[node] updated: prev[node] = CurrentNode visited.add(CurrentNode) return MST

ex: G = [[0, 9, 75, 0, 0], [9, 0, 95, 19, 42], [75, 95, 0, 51, 66], [0, 19, 51, 0, 31], [0, 42, 66, 31, 0]] Edge : Weight 0-1:9 1-3:19 3-4:31 3-2:51