Question 9
Consider the following Python function for cycle detection in an undirected graph represented using an adjacency list.
The function parameters have the following meanings: is the adjacency list representation of an undirected graph with vertices numbered from to . • is the starting vertex from which the function is invoked.• is if vertex has already been visited during the current traversal; otherwise it is . • stores the vertex from which the current vertex was reached during the traversal. For the initial call, may be set to or . • Assume that: The graph may contain one or more connected components.1. The function is called exactly once from a single starting vertex .2. There is no outer loop that invokes the function on other unvisited vertices.3. Which of the following statements is true about the graph traversal strategy used and the portion of the graph on which cycle detection is performed?
The function uses Depth-First Search (DFS) and can detect a cycle only in the connected component containing the starting vertex .
The function uses Breadth-First Search (BFS) and can detect a cycle only in the connected component containing the starting vertex .
The function uses Depth-First Search (DFS) and can detect cycles in all connected components of the graph.
The function uses Breadth-First Search (BFS) and can detect cycles in all connected components of the graph.