$(50)[$Prim$\text{'}$s MST algorithm: tracing$]$ Run the Prim's algorithm implemented using a

priority queue $($see below$)$ against the graph shown below. Give your answers as follows.

a$)$ Run the algorithm assuming the node $a$ is picked as the start node s$,$ and show the algorithm

run trace $($see the specification below$).$

b$)$ Run the algorithm assuming the node $g$ is picked as the start node $s,$ and show the algorithm

run trace $($see the specification below$).$

c$)$ Draw the resulting minimum spanning tree on the graph. Show the included edges in colored

or thick lines.

Specification of the algorithm run tracing: For each algorithm run tracing, show the content of

the cut S$,$ the content of the MST T$,$ and the content of the priority queue Q at the end of the

While loop in each iteration. Specifically, show the content of $S$ as a set of nodes, the content of

$T$ as a set of edges, and the content of $Q$ as a set of ordered pairs of a node number and a priority

key. $($For ease of grading, please show the end nodes of an edge in the alphabetical order $($e$.$g$.,$

$(a,d)),$ and list the priority queue elements in the alphabetic order of node number.$)$ For example,

when the start node is $a,$ their contents before the $1^{st}$ iteration is $S=\{\},T=\{\},$ and $,$

$(b,),(c,),(d,),(e,),(f,),(g,).$

Initialize $Q$ of $V$ with $(v)larr$ for each node $v$ in $V.$

Pick an arbitrary node as the start node s$.$

Slarr$\{\},$Tlarr$\{\},(s)larr0.$

while $(Q$ is not empty$)$

$v=$ExtractMin$(Q).$

Add $v$ to $S.$

if $vs$ then add the edge $(pred(v),v)$ to $T.//$ pred $-=$ "predecessor"

for each edge $e=(v,w)$ such that $w!$inS

if $(c_e<mi\; id="EditorElement\_337776"></mi><mi\; id="EditorElement\_337780">(</mi><mi\; id="EditorElement\_337779">w</mi><mi\; id="EditorElement\_337781">)</mi><mi\; id="EditorElement\_337784">)</mi><mtext\; id="EditorElement\_337758"></mtext><mi\; id="EditorElement\_337759">\{</mi>$

$(w)=c_e,$pred$(w)=v.$

ChangeKey$($Q$,$ w$,(w).$

$\}$

$\}$

endwhile