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
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
Additional Information
No response