2025-253

Consider a graph 

$G=(V,E)$, and the Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms. Analyze the following statements:

I. In a DFS execution on a directed graph, the classification of edges as tree, forward, backward, and cross edges depends on the order in which vertices are explored.

II. In a BFS executed from a source vertex $s$ in an unweighted graph, the order in which vertices are discovered at the same level may vary depending on the order of edges in the adjacency list of the graph, but the minimum distance from each vertex to $s$ remains unchanged.

III. In directed graphs, a back edge detected during DFS indicates the presence of at least one cycle that includes the origin vertex of the edge.

IV. In undirected graphs, BFS can detect all cycles of length 3 (triangles), but it does not guarantee detection of larger cycles.

V. DFS guarantees that in a connected undirected graph, the tree generated contains exactly $\mathrm{\mid }V\mathrm{\mid }-1$ edges, independently of the presence of cycles.

Select the correct alternative:

A) Only I, II, and III are correct.
B) Only II, III, and IV are correct.
C) Only I, III, IV, and V are correct.
D) Only II, III, and V are correct.
E) None of the above.

Original idea by: Mateus de Padua Vicente