The following six questions are about breadth first search and depth first search algorithms on a given graph. Consider an undirected graph 𝐺=(𝑉,𝐸)𝐺=(𝑉,𝐸) given below, where the set of vertices 𝑉={1, 2, 3, 4, 5}𝑉={1, 2, 3, 4, 5} and the set of edges 𝐸={(1, 2),(1, 3),(1, 4),(3, 2),(3, 5)}𝐸={(1, 2),(1, 3),(1, 4),(3, 2),(3, 5)}. We run BFS and DFS algorithms on this graph starting from the vertex 1 which is the initial vertex. Answer the following questions. 1 pointWhich are the three vertices that will be added to the BFS queue in the first step of the BFS algorithm? Does the order in which they are added matter? The three vertices will be 2, 3 and 4, their order will be exactly the same as the one given in this answer option. The three vertices will be 2, 3 and 4, their order does not matter. The three vertices will be 2, 3 and 5, their order will be exactly the same as the one given in this answer option. The three vertices will be 2, 3 and 5, their order does not matter.

In relation to trees, what is the difference between a depth first and breadth first search? 1 pointA depth first will investigate nodes with greater detail, while a breadth first is more superficial in approach. A breadth first is more thorough so will return the result faster. A depth first approach will travel from top to bottom through sibling nodes, while a breadth first will travel through each level.

Compare and contrast depth-first search (DFS) and breadth-first search (BFS) algorithms in graph traversal. Discuss their applications and scenarios where one might be preferred over the other.

Question 8Which of the following are true of breadth-first search? Select all that apply.Breadth-first search is implememted useing a queuebreadth-first search solves the single source shortest path problem in an unwiehgted graph.breadth-first search solves the single source shortest path problem in a wieghted graphbreadth-first search can be used in a directed or undirected graph

The result of a depth-first search of a graph can be conveniently described in terms of a spanning tree of the vertices reached during the search. Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

What is the role of Breadth-First Search (BFS) in graph traversal?A) Ensures shortest path between nodesB) Visits nodes level by level from the start nodeC) Calculates the average distance between nodesD) Finds the maximum flow in a graph