Please solve all questions step by step.

Question 1 Starting from S, trace the operations of the Prims minimum spanning tree algorithm on the graph given in Figure 1

Question 2 Trace the operations of Kruskals minimum spanning tree algorithm on the graph given in Figure 1.

Question 3 Starting from S, trace the operations of breadth-first traversal on the graph given in Figure 1.

Question 4 Given Figure 1 and starting from S ?

a) Trace the operations of depth-first traversal.

b) Give the post-order numbers for all the nodes.

c) Give the pre-order numbers for all the nodes.

d) List the tree arcs, cross arcs, forward arcs, and backward arcs.

N 2 A E 3 3 3 N N 2 S B D G 3 2 1 F Figure 1: A directed weighted graph