Hamiltonian Path and Cycle Finder

Find Hamiltonian paths and cycles in graphs using multiple algorithms. Visualize graph traversal with step-by-step explanations and performance statistics.

Select the number of vertices in your graph (2-15 for performance). For graphs with >12 vertices, use heuristic algorithms.
Click on cells to toggle edges. Diagonal entries are automatically set to 0 (no self-loops).
Enter edges as comma-separated pairs (e.g., "1-2, 2-3, 3-1").

Select a predefined graph example:

Complete Graph K5
Cycle Graph C6
Petersen Graph
Cube Graph Q3
Path Graph P7
Star Graph S6
Random Graph (8 vertices)
Non-Hamiltonian Graph
Complete Graph K8
Wheel Graph W7

Complete Graph K5: Every vertex connected to every other vertex. Many Hamiltonian cycles exist.

Cycle Graph C6: A single cycle connecting all vertices. Exactly one Hamiltonian cycle.

Petersen Graph: Famous non-Hamiltonian graph with 10 vertices.

Export or import graph as JSON. Copy the JSON to save your graph configuration.
Algorithm Selection
Backtracking (Exact)
Nearest Neighbor (Heuristic)
Random Search (Heuristic)
Greedy (Heuristic)
Backtracking: Exact algorithm, guaranteed to find if exists (slow for large graphs). Heuristic algorithms: Faster but may not find solution even if it exists.

Algorithm Controls

Find a path that visits each vertex exactly once
Find a cycle that visits each vertex exactly once and returns to start
Finding Hamiltonian path/cycle...

Understanding Hamiltonian Paths and Cycles

In graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle (starts and ends at the same vertex).

Key Definitions:

  • Hamiltonian Path: A path that visits each vertex exactly once.
  • Hamiltonian Cycle: A Hamiltonian path that starts and ends at the same vertex.
  • Hamiltonian Graph: A graph that contains a Hamiltonian cycle.
  • Traceable Graph: A graph that contains a Hamiltonian path.

Hamiltonian vs Eulerian

Property Hamiltonian Eulerian
Visits Each vertex exactly once Each edge exactly once
Complexity NP-Complete (no known efficient algorithm) Polynomial time (O(E))
Necessary Condition No known simple necessary and sufficient condition All vertices have even degree
Sufficient Condition Dirac's Theorem: deg(v) ≥ n/2 for all vertices Graph is connected and all vertices have even degree
Example Traveling Salesman Problem Seven Bridges of Königsberg

Finding Hamiltonian Paths/Cycles

1

Backtracking Algorithm: This calculator uses a backtracking approach to explore all possible paths. The algorithm tries to extend the current path by adding an unvisited neighbor, backtracking when no extension is possible.

Time Complexity: O(n!) in worst case
2

Optimizations: The algorithm includes pruning techniques like checking if the remaining graph is connected, and using degree constraints to reduce the search space.

3

Visualization: The step-by-step visualization shows how the algorithm explores the graph, backtracks when needed, and eventually finds a Hamiltonian path or cycle if one exists.

Applications of Hamiltonian Paths

  • Traveling Salesman Problem: Finding the shortest route visiting all cities exactly once and returning to the origin
  • DNA Sequencing: Reconstructing DNA sequences from fragments
  • Circuit Design: Designing circuits that visit all nodes exactly once
  • Game Solving: Solving puzzles like the Knight's Tour on a chessboard
  • Network Routing: Designing routes that visit all nodes in a network

Calculator Features:

  • Interactive graph visualization with drag-and-drop vertices
  • Multiple input methods: adjacency matrix, edge list, or predefined examples
  • Step-by-step algorithm visualization with playback controls
  • Find both Hamiltonian paths and cycles
  • Detailed explanation of algorithm steps and results

Frequently Asked Questions

A Hamiltonian path visits each vertex exactly once, while an Eulerian path visits each edge exactly once. Finding Hamiltonian paths is NP-complete (no known efficient algorithm), while Eulerian paths can be found in polynomial time.

Yes, if a graph has a Hamiltonian cycle, it automatically has a Hamiltonian path (just remove one edge from the cycle). However, a graph can be traceable (have a Hamiltonian path) without having a Hamiltonian cycle.

The Hamiltonian path problem is NP-complete, which means there's no known algorithm that can solve it efficiently for all cases. The brute-force approach tries all n! possible permutations of vertices, which becomes infeasible for graphs with more than about 15 vertices.

Dirac's theorem states that a simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree at least n/2. This is a sufficient condition but not necessary - some Hamiltonian graphs don't satisfy this condition.

Currently, this tool only handles undirected graphs. For directed graphs (digraphs), the Hamiltonian path problem is also NP-complete but requires a different algorithm that considers edge directions.