Question

Identify the correct statements about DFS traversal of graph.
(i) It can be used to determine whether a graph is cycle or not
(ii) It identifies the connected components of an undirected graph
(iii) Traverses a single path of the graph until it visits a node with no successor.

• A. (i) and (ii)
• B. (ii) and (iii)
• C. (i) and (iii)
• D. (i), (ii) and (iii)

Answer 1

The correct option is D (i), (ii) and (iii)

DFS traversal of the graph:-
(i) It can be used to determine whether a graph is a cycle or not
(ii) It identifies the connected components of an undirected graph
(iii) Traverses a single path of the graph until it visits a node with no successor.

Depth-first traversal for a graph is similar to depth-first traversal tree. Unlike trees, graphs may contain cycles, so it may come to the same node again. To avoid processing a node more than once, it uses a Boolean visited array.

Depth First Search (DFS) algorithm traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search when a dead end occurs in any iteration.