Given the following graph

a$)$ Use Prim$$s algorithm to find an MST$.$ You need to show your intermediate steps by filling in the table below and highlighting the MST in the graph.

$$ Note: in case there are multiple choices, choose the vertex with smaller number.

Q

d

VA

Min$($Q$)$

$\{0,1,2,3,4,5,6,7,8\}$

$\{0,$$,$$,$$,$$,$$,$$,$$,$$\}$

$$

$0$

$\{1,2,3,4,5,6,7,8\}$

$\{0,8,$ $,$ $,$ $,$ $,$ $,8,$ $\}$

$\{0\}$

$1$

$\{2,3,4,5,6,7,8\}$

$\{0,8,2,$ $,$ $,$ $,$ $,8,$ $\}$

$\{0,1\}$

$2$

$\{3,4,5,6,7,8\}$

$\{0,8,2,7,$ $,4,$ $,8,2\}$

$\{0,1,2\}$

$5$

$\{3,4,6,7,8\}$

$\{0,8,2,7,10,4,6,8,2\}$

$\{0,1,2,5\}$

$8$

$\{3,4,6,7\}$

$\{0,8,2,7,10,4,6,7,2\}$

$\{0,1,2,5,8\}$

$6$

$\{3,4,7\}$

$\{0,8,2,7,10,4,6,7,2\}$

$\{0,1,2,5,8,6\}$

$7$

$\{3,4\}$

$\{0,8,2,7,10,4,6,7,2\}$

$\{0,1,2,5,8,6,7\}$

$3$

$\{4\}$

$\{0,8,2,7,9,4,6,7,2\}$

$\{0,1,2,5,8,6,7,3\}$

$4$

$$

$$

$\{0,1,2,5,8,6,7,3,4\}$

$$

$(0,1),(1,2),(2,5),(2,8),(5,6),(8,7),(3,4),(7,3).$

$$

$$

b$)$ Use Kruskal$$s algorithm to find an MST$.$ You need to show your intermediate steps by filling in the table below and highlighting the MST in the graph.

$$ Note: in case there are multiple choices, choose the vertex with smaller number.

$$

Edge considered

Weight

Sets of connected vertices

$\{0\}\{1\}\{2\}\{3\}\{4\}\{5\}\{6\}\{7\}\{8\}$