New Upcoming Legal Jobs Free Workshop March 11 at 5 PM. Register here

    Question

    Which of the following traversal algorithms is

    guaranteed to visit all vertices in the minimum number of edges in an unweighted graph?
    A Depth-First Search (DFS) Correct Answer Incorrect Answer
    B Breadth-First Search (BFS) Correct Answer Incorrect Answer
    C Dijkstra’s Algorithm Correct Answer Incorrect Answer
    D Prim’s Algorithm Correct Answer Incorrect Answer
    E Bellman-Ford Algorithm Correct Answer Incorrect Answer

    Solution

    In an unweighted graph, Breadth-First Search (BFS) is optimal for finding the shortest path in terms of the number of edges. BFS explores all vertices at the current depth level before moving on to the next level, ensuring that the shortest path is found when the destination vertex is first encountered. For unweighted graphs, the edge count represents the path cost, and BFS efficiently identifies the shortest path by expanding vertices layer by layer. Why Other Options Are Incorrect: 1. Depth-First Search (DFS): DFS explores as far as possible along a branch before backtracking, which does not guarantee the shortest path in terms of edges. 2. Dijkstra’s Algorithm: While Dijkstra’s algorithm is used for weighted graphs, it is not necessary for unweighted graphs where BFS suffices. 3. Prim’s Algorithm: Prim’s algorithm is used for finding minimum spanning trees, not shortest paths. 4. Bellman-Ford Algorithm: While Bellman-Ford can handle negative weights, it is computationally expensive compared to BFS for unweighted graphs.

    Practice Next