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, characterized by its recursive stack-based exploration of graph nodes.

Step-by-step explanation:

The approach used in the given pseudocode for graph traversal is Depth First Search (DFS). This is identified by the use of a recursive function that marks a node as visited, then iterates through all unvisited neigh boring nodes and recursively visits them. In contrast to BFS which uses a queue DFS uses a stack which can be implicitly implemented using recursion as shown in the pseudocode.