Note: This should be an undirected graph. To change or eliminate a connection, it must be done using both nodes. When the tree is constructed, note that connections are made, for example, both between nodes $(0$ and $1)$ and $(1$ and $0),$ with the same weights.

# Prim's Python implementation of the Minimum Spanning Tree

class Node :

def $\_\_$init$\_\_($self$,$ arg$\_$id$)$ :

self.$\_$id $=$ arg$\_$id

class Graph :

def $\_\_$init$\_\_($self$,$ arg$\_$source, arg$\_$adj$\_$list$)$ :

self.source $=$ arg$\_$source

self.adjlist $=$ arg$\_$adj$\_$list

def PrimsMST$($self$)$:

# Priority queue is implemented as a dictionary with

# key as an object of 'Node' class and value as the cost of

# reaching the node from the source.

# Since the priority queue can have multiple entries for the

# same adjacent node but a different cost, we have to use objects as

# keys so that they can be stored in a dictionary.

# $[$As dictionary can't have duplicate keys so objectify the key$]$

# The distance of source node from itself is $0.$ Add source node as the first node

# in the priority queue

priority$\_$queue $=\{$ Node$($self$.$source$)$ : $0\}$

added $=[$False$]*$ len$($self$.$adjlist$)$

min$\_$span$\_$tree$\_$cost $=0$

while priority$\_$queue :

# Choose the adjacent node with the least edge cost

node $=$ min $($priority$\_$queue, key$=$priority$\_$queue.get$)$

cost $=$ priority$\_$queue$[$node$]$

# Remove the node from the priority queue

del priority$\_$queue$[$node$]$

if added$[$node$.\_$id$]==$ False :

min$\_$span$\_$tree$\_$cost $+=$ cost

added$[$node$.\_$id$]=$ True

print$("$Added Node : $"+$ str$($node$.\_$id$)+",$ cost now : $"+$str$($min$\_$span$\_$tree$\_$cost$))$

for item in self.adjlist$[$node$.\_$id$]$ :

adjnode $=$ item$[0]$

adjcost $=$ item$[1]$

if added$[$adjnode$]==$ False :

priority$\_$queue$[$Node$($adjnode$)]=$ adjcost

return min$\_$span$\_$tree$\_$cost

def main$()$ :

g$1\_$edges$\_$from$\_$node $=\{\}$

# Outgoing edges from the node: $($adjacent$\_$node, cost$)$ in graph.

g$1\_$edges$\_$from$\_$node$[0]=[(1,1),(2,2),(3,1),(4,1),(5,2),(6,1)]$

g$1\_$edges$\_$from$\_$node$[1]=[(0,1),(2,2),(6,2)]$

g$1\_$edges$\_$from$\_$node$[2]=[(0,2),(1,2),(3,1)]$

g$1\_$edges$\_$from$\_$node$[3]=[(0,1),(2,1),(4,2)]$

g$1\_$edges$\_$from$\_$node$[4]=[(0,1),(3,2),(5,2)]$

g$1\_$edges$\_$from$\_$node$[5]=[(0,2),(4,2),(6,1)]$

g$1\_$edges$\_$from$\_$node$[6]=[(0,1),(1,2),(5,1)]$

g$1=$ Graph$(0,$ g$1\_$edges$\_$from$\_$node$)$

cost $=$ g$1.$PrimsMST$()$

print$("$Cost of the minimum spanning tree is : $"+$ str$($cost$)+"$

$")$

if $\_\_$name$\_\_=="\_\_$main$\_\_"$ :

main$()$

#This is the end!

Note the order the nodes were added and the cost in the output window.

Output:

Procedure Part $1$:

$1.$ Use graphonline to draw the graph created above, including the weights. Use the vertex enumeration option to set the node numbers. run the minimum spanning tree algorithm. Check that the MST weight is the same as the algorithm above. Graphonline:

Using graphonline.ru

$2.$ Take a screenshot

$3.$ Modify the given Prims$$s code by doing the following:

Change the weight from node $0$ to node $6$ to $3$

Change the weight from node $2$ to node $3$ to $7$

Eliminate the connection between nodes $0$ and $4$

$4.$ Run the program and determine the weight of the minimum spanning tree

Copy the entire Spyder wi