(i) Select a root node (lab A in our case) Mark the root node as Reached...

Transcribed Image Text:

(i) Select a root node (lab A in our case) Mark the root node as Reached Mark all the other nodes in the graph as Unreached (ii) Find an edge with minimum weight in the graph that connects a Reached node to an Unreached node. (Use alphabetical order to break ties (e.g., between edges (C,H) and (F,H), choose (C,H)) (iii) Add the found edge to MST, and mark its endpoint nodes as Reached (iv) Repeat the steps (ii) and (iii) until all nodes in the graph have become Reached (d) (8 points) Draw the MST obtained by Prim's algorithm on the figure below (by indicating the selected edges in very thick straight lines). Mention the selected edges in the order of selection by the algorithm. C A B H D F E G (e) (4 points) What type of an algorithm is Prim's algorithm? Name one advantage and one disadvantage of such algorithms. (i) Select a root node (lab A in our case) Mark the root node as Reached Mark all the other nodes in the graph as Unreached (ii) Find an edge with minimum weight in the graph that connects a Reached node to an Unreached node. (Use alphabetical order to break ties (e.g., between edges (C,H) and (F,H), choose (C,H)) (iii) Add the found edge to MST, and mark its endpoint nodes as Reached (iv) Repeat the steps (ii) and (iii) until all nodes in the graph have become Reached (d) (8 points) Draw the MST obtained by Prim's algorithm on the figure below (by indicating the selected edges in very thick straight lines). Mention the selected edges in the order of selection by the algorithm. C A B H D F E G (e) (4 points) What type of an algorithm is Prim's algorithm? Name one advantage and one disadvantage of such algorithms.