Question

Following is a pseudocode for a graph traversal technique: traversal-recursive(G, s): mark s as visited for all neighbours w of s in Graph G: if w is not visited: traversal-recursive(G, w). What is the approach used in this pseudocode?

1) Breadth First Search
2) Depth First Search
3) Dijkstra's Algorithm
4) Prim's Algorithm

Answer 1

The pseudocode represents the Depth First Search (DFS) algorithm, which is a graph traversal technique that explores as far as possible along each branch before backtracking.

Step-by-step explanation:

The pseudocode provided is for a graph traversal technique and its approach is to mark a node as visited and then recursively visit all of its unvisited neighbors. This approach is characteristic of a Depth First Search (DFS), which is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking. So, the correct answer to the question is option 2) Depth First Search.