Questão 1
Consider
the Depth-First Search (DFS) algorithm applied to a directed graph. Determine
whether the following statements are true or false:
1- 1- In the DFS algorithm, if a vertex is visited, it will never be revisited. Therefore, by the end of the algorithm's execution, all vertices in the graph will have been visited once, assuming the graph is connected.
2- 2- When a vertex u is explored in DFS, its neighbors are explored in an order that depends on the graph structure. If a vertex v is a neighbor of u and has not been visited yet, it will be visited immediately after u.
3- 3- In DFS, the order in which vertices
are visited can be used to construct a cycle and detect if a graph contains
cycles.
Mark which
alternatives are correct:
a- 1 and 2
b- 2 and 3
c- 3
d- 1 and 3
e- None of the above
Interesting question, but statement (3) is a bit confusing. If there is no cycle, the DFS cannot construct a cycle as mentioned, can it?
ResponderExcluir