#Task $2$

from graph import $*$

G $=$ Graph$()$

for i in $[\text{'}$A$\text{'},\text{'}$B$\text{'},\text{'}$C$\text{'},\text{'}$D$\text{'},\text{'}$E$\text{'},\text{'}$F$\text{'},\text{'}$G$\text{'},\text{'}$H$\text{'},\text{'}$I$\text{'}]$:

G$.$addVertex$($ Node$($i$))$

V $=$ G$.$vertices

#$0,1,2,3,4,5,6,7,8$

#A$,$ B$,$ C$,$ D$,$ E$,$ F$,$ G$,$ H$,$ I

G$.$addBiEdge$($ V$[0],$ V$[1],4)$

G$.$addBiEdge$($ V$[0],$ V$[7],8)$

G$.$addBiEdge$($ V$[1],$ V$[7],11)$

G$.$addBiEdge$($ V$[1],$ V$[2],8)$

G$.$addBiEdge$($ V$[2],$ V$[3],7)$

G$.$addBiEdge$($ V$[3],$ V$[4],9)$

G$.$addBiEdge$($ V$[3],$ V$[5],14)$

G$.$addBiEdge$($ V$[4],$ V$[5],10)$

G$.$addBiEdge$($ V$[2],$ V$[5],4)$

G$.$addBiEdge$($ V$[2],$ V$[8],2)$

G$.$addBiEdge$($ V$[5],$ V$[6],2)$

G$.$addBiEdge$($ V$[6],$ V$[7],1)$

G$.$addBiEdge$($ V$[6],$ V$[8],6)$

G$.$addBiEdge$($ V$[7],$ V$[8],7)$

# G is graph

# s is the node to start

def slowPrim$($G$,$ s$)$:

# first, find the lightest edge leaving s

bestWt $=$ np$.$inf

bestu $=$ None

for u$,$wt in s$.$getOutNeighborsWithWeights$()$:

if wt $<$ bestWt:

bestWt $=$ wt

bestu $=$ u

MST $=[($s$,$ bestu$)]$

verticesVisited $=[$s$,$bestu$]$

while len$($verticesVisited$)<$ len$($G$.$vertices$)$: # danger! this will loop forever if the graph isn't connected...

# find the lightest edge $($x$,$v$)$ so that x has been visited and v hasn't.

bestWt $=$ np$.$inf

bestv $=$ None

bestx $=$ None

for x in verticesVisited:

for v$,$wt in x$.$getOutNeighborsWithWeights$()$:

if v in verticesVisited:

continue

if wt $<$ bestWt:

bestWt $=$ wt

bestv $=$ v

bestx $=$ x

MST$.$append$(($bestx$,$bestv$))$

verticesVisited.append$($bestv$)$

return MST

T $=$ slowPrim$($G$,$ G$.$vertices$[0])$

for x$,$y in T:

print$($x$,$y$)$

The above code works but is slow. I need it optimised.

This is the task question. Please leave detailed comments in the code and an explanation after to help me understand