[FEATURE REQUEST] Hamiltonian Cycle Detection and Path Calculation Algorithm using Backtracking

[Vanshika-Dargan]

What would you like to Propose?

Problem Name: Hamiltonian Cycle Detection and Path Calculation Algorithm.

Problem Statment:

Given an undirected graph, the task is to determine whether the graph contains a Hamiltonian cycle or not. If it contains, then
print the path.

Hamiltonian Cycle in a graph is a cycle that visits every vertex of graph exactly once and returns to the starting vertex.

Example:-
Input:- graph:
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4)
Output: 0 -> 1 -> 2 -> 4 -> 3 -> 0

Issue details

Here is the algorithm that can solve this problem optimally.
class HamiltonianCycle:
V // Number of vertices in the graph
path[V] // To store the Hamiltonian Cycle Path
visited // Set to keep track of visited vertices

constructor HamiltonianCycle(V):
    this.V = V
    path = new Array of size V
    visited = new Set()

method printPath():
    for i from 0 to V-1:
        print path[i] + " -> "
    print path[0]

method hamiltonianCycleUtil(graph, curr):
    if curr is equal to V:
        if graph[path[curr - 1]][path[0]] is equal to 1:
            return true
        else:
            return false

    for i from 0 to V-1:
        if i is not in visited and graph[path[curr - 1]][i] is equal to 1:
            path[curr] = i
            visited.add(i)
            if hamiltonianCycleUtil(graph, curr + 1) is true:
                return true
            visited.remove(visited.size()-1)

    return false

method findHamiltonianCycle(graph, vertices):
    create an instance of HamiltonianCycle with vertices

    path[0] = 0
    visited.add(0)

    if hamiltonianCycleUtil(graph, 1) is true:
        printPath()
        return 1
    else:
        print "No Hamiltonian cycle found"
        return 0

Additional Information

No response

[github-actions]

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

[github-actions]

Please reopen this issue once you have made the required changes. If you need help, feel free to ask in our Discord server or ping one of the maintainers here. Thank you for your contribution!