Name and describe two graph traversal algorithms and their use cases.

Name and describe two graph traversal algorithms and their use cases.

• A. Breadth-first search explores level by level and is useful for shortest paths in unweighted graphs; Depth-first search explores as deep as possible and is useful for path discovery and topological ordering.
• B. Cycle detection is BFS's primary use.
• C. DFS is used for finding shortest paths.
• D. BFS and DFS are identical.

Answer: (A)

Two fundamental graph traversal methods are breadth-first search and depth-first search. Breadth-first search explores the graph level by level, visiting all neighbors of a node before moving on to the next level. Because it discovers nodes in order of their distance from the start, it provides the shortest path (in terms of number of edges) in unweighted graphs, which is why it’s the go-to method for shortest-path problems and for understanding how far nodes are from the starting point. Depth-first search, on the other hand, dives as deep as possible along a branch before backtracking. This deep exploration makes it excellent for finding a path between two nodes and for tasks that depend on the ordering of discovery, such as producing a topological ordering in directed acyclic graphs. The finish times in DFS reveal the dependency structure, which is key for ordering tasks that must happen after prerequisites. So the description that matches these capabilities—BFS for level-by-level exploration and shortest paths in unweighted graphs, and DFS for deep path discovery and topological ordering—is the best fit.

Two fundamental graph traversal methods are breadth-first search and depth-first search. Breadth-first search explores the graph level by level, visiting all neighbors of a node before moving on to the next level. Because it discovers nodes in order of their distance from the start, it provides the shortest path (in terms of number of edges) in unweighted graphs, which is why it’s the go-to method for shortest-path problems and for understanding how far nodes are from the starting point.

Depth-first search, on the other hand, dives as deep as possible along a branch before backtracking. This deep exploration makes it excellent for finding a path between two nodes and for tasks that depend on the ordering of discovery, such as producing a topological ordering in directed acyclic graphs. The finish times in DFS reveal the dependency structure, which is key for ordering tasks that must happen after prerequisites.

So the description that matches these capabilities—BFS for level-by-level exploration and shortest paths in unweighted graphs, and DFS for deep path discovery and topological ordering—is the best fit.