In a Depth First Search (DFS) traversal, what is the purpose of marking nodes…
2025
In a Depth First Search (DFS) traversal, what is the purpose of marking nodes as visited?
- A.
To avoid revisiting nodes and prevent infinite loops
- B.
To keep track of the parent node
- C.
To prioritize nodes
- D.
To find the shortest path
Attempted by 187 students.
Show answer & explanation
Correct answer: A
In Depth First Search (DFS), marking nodes as visited is a critical mechanism to ensure the algorithm terminates correctly and efficiently. When traversing a graph, especially one containing cycles or multiple paths to the same node, DFS might otherwise revisit nodes endlessly. By maintaining a visited set, the algorithm checks if a neighbor has already been processed before exploring it further. This prevents infinite loops in cyclic graphs and ensures each node is visited exactly once, leading to a linear time complexity relative to the graph size.