FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Hamiltonian Cycle



Introduction

A Hamiltonian Cycle is a cycle in a graph that visits every vertex exactly once and finally returns to the starting vertex. It is one of the most important applications of the Backtracking technique and is widely studied in graph theory, optimization and computer science.

Unlike an Euler Cycle, which visits every edge exactly once, a Hamiltonian Cycle focuses on visiting every vertex exactly once.

Problem Statement

Given a graph containing N vertices, determine whether a cycle exists that visits every vertex exactly once before returning to the starting vertex.

Why Backtracking?

The algorithm tries different possible paths one by one. If the current path cannot be extended into a valid Hamiltonian Cycle, it returns to the previous vertex and explores another path. This process is known as Backtracking.

Characteristics of Hamiltonian Cycle

Property Description
Visits every vertex Each vertex is visited exactly once.
Returns to Start The last vertex must connect to the starting vertex.
No Repeated Vertices A vertex cannot appear twice except the starting vertex.
Graph Traversal Applicable to connected graphs.

Graph Illustration


        A

      /   \

     B-----C

      \   /

        D

Hamiltonian Cycle

A → B → D → C → A

Figure 1 : Hamiltonian Cycle

Real-Life Example

Suppose a delivery vehicle must visit each customer exactly once and finally return to the warehouse. The route should include every customer exactly one time without repetition. This situation resembles the Hamiltonian Cycle Problem.

Solved Example

Consider the graph shown above.

Step Visited Vertex Status
1 A Start
2 B Valid
3 D Valid
4 C Valid
5 A Cycle Completed

State Space Tree


             Start(A)

          /      |      \

         B       C       D

         |

         D

         |

         C

         |

      Hamiltonian Cycle

Figure 2 : State Space Tree

Difference Between Hamiltonian Cycle and Euler Cycle

Hamiltonian Cycle Euler Cycle
Visits every vertex exactly once. Visits every edge exactly once.
Vertices are important. Edges are important.
Backtracking based solution. Graph traversal based solution.
Generally NP-Complete. Polynomial-time solution exists.

Hamiltonian Cycle Algorithm

HamiltonianCycle(Vertex) Step 1 : Add the starting vertex to the path. Step 2 : Select an adjacent unvisited vertex. Step 3 : Check whether the selected vertex is safe. Step 4 : Add the vertex to the current path. Step 5 : Recursively repeat the process for the next vertex. Step 6 : If no valid vertex exists, Remove the last vertex (Backtrack). Step 7 : If all vertices are visited and the last vertex is connected to the first vertex, Hamiltonian Cycle Found.

Dry Run

Consider the graph containing four vertices A, B, C and D.

Step Current Path Status
1 A Start
2 A → B Valid
3 A → B → D Valid
4 A → B → D → C Valid
5 A → B → D → C → A Hamiltonian Cycle Found

Complexity Analysis

Parameter Complexity Remarks
Best Case O(V) Valid cycle is found quickly.
Average Case Problem Dependent Depends upon graph connectivity.
Worst Case O(V!) Many possible paths may need to be explored.
Space Complexity O(V) Recursive call stack and path array.

Advantages of Hamiltonian Cycle

  • Finds a valid Hamiltonian Cycle whenever one exists.
  • Uses pruning to avoid unnecessary search.
  • Suitable for constraint satisfaction problems.
  • Simple recursive implementation using Backtracking.
  • Useful in many routing and scheduling applications.

Limitations of Hamiltonian Cycle

  • Worst-case time complexity is factorial.
  • Execution time increases rapidly as the number of vertices increases.
  • Requires recursive function calls.
  • Not suitable for very large graphs without optimization.

Applications of Hamiltonian Cycle

Application Description
Route Planning Finding routes that visit every location exactly once.
Robot Navigation Planning efficient movement paths.
Circuit Design Testing electronic circuits.
DNA Sequencing Genome sequencing and analysis.
Network Design Efficient traversal of communication networks.

Hamiltonian Cycle vs Travelling Salesman Problem

Hamiltonian Cycle Travelling Salesman Problem
Visits every vertex exactly once. Visits every city exactly once with minimum total cost.
Focuses on existence of a cycle. Focuses on finding the minimum-cost tour.
Edge weights are not mandatory. Edge weights (cost/distance) are essential.
Solved using Backtracking. Solved using Backtracking, Dynamic Programming or Branch and Bound.
Decision Problem. Optimization Problem.

💡 Remember This

Visit Every Vertex Exactly Once

Return to the Starting Vertex

A Hamiltonian Cycle must satisfy both conditions.

Important Points

  • A Hamiltonian Cycle visits every vertex exactly once.
  • The cycle must end at the starting vertex.
  • Backtracking removes invalid paths and explores alternatives.
  • The algorithm uses a State Space Tree.
  • Worst-case time complexity is O(V!).
  • Hamiltonian Cycle is different from Euler Cycle.

💼 Interview Corner

  • What is a Hamiltonian Cycle?
  • How is a Hamiltonian Cycle different from an Euler Cycle?
  • Why is Backtracking suitable for the Hamiltonian Cycle Problem?
  • What is the difference between Hamiltonian Cycle and Travelling Salesman Problem?
  • State the worst-case time complexity of the Hamiltonian Cycle algorithm.

🎓 AKTU Examination Tip

AKTU examinations frequently ask students to define a Hamiltonian Cycle, explain the Backtracking algorithm, solve a small graph example, compare Hamiltonian Cycle with Euler Cycle or Travelling Salesman Problem, and discuss its practical applications.

Summary

The Hamiltonian Cycle Problem is a classical Backtracking problem that determines whether a graph contains a cycle visiting every vertex exactly once before returning to the starting vertex. The algorithm systematically explores all possible paths and backtracks whenever an invalid path is encountered. Although the worst-case time complexity is O(V!), Backtracking significantly reduces unnecessary exploration through pruning.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com