cise $1$: $($M$|$S$)$PT $(25$ Points$)$

der the graph $G$ given below.

For each of the following, draw the

minimum spanning tree at each step of

$($a$)$ Kruskal's Algorithm.

$($b$)$ Prim's Algorithm. Start with vertex $a$ as the root.

$($c$)$ For each of the above algorithms, show the cut that validates the addition of the edge

$(a,b)$ in your MST$.$

shortest path tree with vertex $a$ as the root at each step of

$($a$)$ Dijkstra's Algorithm.

$($b$)$ Bellman Ford Algorithm