Hamiltonian Circuit Problem in DAA

Learn the Hamiltonian Circuit Problem in DAA using the Backtracking method. Understand the algorithm, isSafe condition, difference between Hamiltonian Path and Circuit, time complexity O(N!), and applications like TSP.

Hamiltonian Circuit Problem in DAA

Introduction

The Hamiltonian Circuit Problem is a backtracking-based graph problem.
In a given graph, the objective is to find a cycle (circuit) such that:

Each vertex is visited exactly once
The path finally returns to the starting vertex

Problem Statement

Given an Undirected or Directed Graph
G(V, E)

Objective:

• Each vertex must be visited only once
• Determine whether a closed path (cycle) exists in the graph

Difference between Hamiltonian Path and Hamiltonian Circuit

Concept of Backtracking

• The path is constructed vertex by vertex
• Each next vertex is checked to determine whether it is valid
• If it is not possible to proceed further, the algorithm backtracks and tries another vertex

Valid Vertex Conditions

To add a vertex to the path:

1. The vertex must be adjacent to the previous vertex
2. The vertex must not have been visited earlier

Hamiltonian Circuit Algorithm (Backtracking)

Hamiltonian(pos)
{
if (pos == n)
{
if (graph[path[pos – 1]][path[0]] == 1)
print solution
else
return
}

for v = 1 to n – 1
{
if (isSafe(v, pos))
{
path[pos] = v
Hamiltonian(pos + 1)
path[pos] = -1   // Backtrack
}
}
}

isSafe(v, pos) Condition

• Check whether v is adjacent to path[pos − 1]
• Check whether v has not been used earlier in the path

Example

For a graph with four vertices, a Hamiltonian circuit can be:

1 → 2 → 3 → 4 → 1

Time Complexity

• Worst Case Time Complexity: O(N!)
• Because all possible permutations of vertices may need to be checked

Space Complexity

• O(N) – To store the path array
• O(N) – Recursive call stack

Advantages of the Hamiltonian Circuit Problem

• Useful for understanding graph traversal problems
• Forms the basis for the Travelling Salesman Problem (TSP)
• Clearly explains the backtracking technique

Limitations

• It is an NP-Complete problem
• Becomes time-consuming for large graphs

Applications of the Hamiltonian Circuit Problem

• Network Routing
• DNA Sequencing
• Travelling Salesman Problem
• Circuit Design

Conclusion

The Hamiltonian Circuit Problem is an important problem that demonstrates the
limitations of algorithmic power.
It can be effectively explained and solved using the Backtracking method for smaller input sizes.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1