Question
Circle the number or the number of the answer which best completes the sentence. A. Which of the following is Depth-First Search traversal of a graph represented by the above adjacency list starting at 1? (for RECURSIVE algorithm, below F.) 1, 2, 3, 4, 5 1, 2, 5, 4, 3 1, 2, 4, 5, 3 1, 2, 4, 3, 5 B. Which of the following is a Breadth-First Search traversal of the graph represented by the above adjacency list starting at 3? 3, 1, 5, 2, 4 3, 1, 2, 5, 4 3, 1, 2, 4, 5 3, 1, 5, 4, 2 C. For the above graph, which of the following is a spanning tree? AE, CE, CD, BD AC, CD, BD, AB AB, AC, CE, AE AE, AC, CE, BD D. Using Kruskal's minimum spanning tree algorithm, which are the first 2 edges added the minimum spanning tree? AB, BD AC, AE BD, CD AC, CD E. Using Prim's minimum spanning tree algorithm, which are the first 2 edges added to the minimum spanning tree if we start at vertex A? AB, BD AC, AE AE, CD AC, BD F. Which algorithm finds all the shortest paths from one vertex to all the other vertices? Kruskal's AVL Dikjstra's Prim's GRAPH DPS RECURSIVE ALGORITHM (for MULTIPLE CHOICE) DFS(0, y): label v as visited for all edges from v to w in G. adjacent Edges (v) do if vertex w is net labeled as visited then recursively call DFS(G, w) end if end for
Explanation / Answer
Part A) Option 3 is correct.
Because the search will be completed in following way :(repeated values will be skipped)
Part B) Option 3 is correct.
As it is BFS so the algorithm will traverse its adjecent nodes without following hierarchy.
3->1->2->4->5
Part C) Option 1 is correct.
As spanning tree is one which traverses all the edges of the graph using the least number of edges and it can not be disconnected.
Part D) Option 3 is correct.
Because, acoording to Kruskal's algorithm the edges with the least weight are selected first.
Part E) Option 1 is correct.
Because, according to Prim's algorithm we move to that node whose weight is minimum and is adjecent to the given starting node.
Part F) Option 3 is correct.
Beacuse in Dikjstra's algorithm we form shortest path tree set which keeps tracks of the distance from a single node to all other vertices and by that we can find the shortest path from one vertex to all other vertices.
Kindly rate my answer.ThankYou.