New NABARD Workshop - Last 4 year trend. March 5 at 5 PM. Register here

    Question

    Which algorithm is best suited for finding a Hamiltonian

    cycle in an undirected graph?       
    A Depth First Search Correct Answer Incorrect Answer
    B Bellman-Ford Algorithm Correct Answer Incorrect Answer
    C Backtracking Correct Answer Incorrect Answer
    D Kruskal’s Algorithm Correct Answer Incorrect Answer
    E Floyd-Warshall Algorithm Correct Answer Incorrect Answer

    Solution

    Backtracking is a general algorithmic technique used for solving problems incrementally, such as finding a Hamiltonian cycle, where a solution is built step-by-step. Backtracking tries all possibilities and retreats when a solution is not feasible, making it ideal for problems like Hamiltonian cycles that require exhaustive search with constraints. Why Other Options are Wrong: a) DFS can traverse a graph but is not designed to find Hamiltonian cycles. b) Bellman-Ford is used for finding shortest paths, not cycles. d) Kruskal’s Algorithm is for Minimum Spanning Trees, not Hamiltonian cycles. e) Floyd-Warshall is for finding shortest paths between all pairs of nodes.

    Practice Next