---

📘 Hamiltonian Circuit Problem

1️⃣ Introduction

The Hamiltonian Circuit Problem is a classic problem in graph theory and algorithm design.

🔹 Definition

A Hamiltonian Circuit (or Hamiltonian Cycle) is a closed path in a graph that:

• Visits each vertex exactly once
• Returns to the starting vertex

A graph that contains a Hamiltonian circuit is called a Hamiltonian graph.

---

2️⃣ Problem Statement

Given a graph G(V, E), determine whether there exists a Hamiltonian Circuit that:

• Starts from a vertex
• Visits all vertices exactly once
• Ends at the same starting vertex

---

3️⃣ Key Characteristics

• Each vertex appears once (except start/end)
• Circuit must include all vertices
• Applicable to directed and undirected graphs
• Different from Euler Circuit (edges vs vertices)

---

4️⃣ Why Hamiltonian Circuit is Difficult

• Number of possible paths grows factorially
• Requires checking all permutations of vertices
• No known polynomial-time solution

📌 Hence, it belongs to the class of NP-Complete problems

---

5️⃣ Hamiltonian Circuit Using Backtracking

🔹 Why Backtracking?

• Try one vertex at a time
• If a partial path violates constraints, backtrack
• Prune invalid paths early

---

6️⃣ Representation

• Graph represented using adjacency matrix
• Use an array path[] to store the current path

📌 path[i] stores the vertex at position i in the Hamiltonian path

---

7️⃣ Algorithm Logic (Backtracking Approach)

🔹 Steps

1. Start from vertex 0
2. Add one vertex at a time to the path
3. Check:
   • Vertex is not already included
   • There is an edge from previous vertex
4. If path includes all vertices:
   • Check edge from last vertex to first
5. If not valid, backtrack

---

8️⃣ Pseudocode for Hamiltonian Circuit

HamiltonianCircuit(path, pos):
   if pos == n:
       if graph[path[pos-1]][path[0]] == 1:
           return true
       else
           return false

   for v = 1 to n-1:
       if isSafe(v, path, pos):
           path[pos] = v
           if HamiltonianCircuit(path, pos + 1):
               return true
           path[pos] = -1   // backtrack
   return false

---

🔹 isSafe Function

isSafe(v, path, pos):
   if graph[path[pos-1]][v] == 0:
       return false
   if v is already in path:
       return false
   return true

---

9️⃣ Example

🔹 Graph with 4 Vertices

Vertices: {0, 1, 2, 3}

One Hamiltonian Circuit:

0 → 1 → 2 → 3 → 0

✔ Visits all vertices once
✔ Returns to starting vertex

---

🔟 Time and Space Complexity

🔹 Time Complexity

• Worst Case: O(n!)
• Due to checking all permutations of vertices

🔹 Space Complexity

• Path array: O(n)
• Recursion stack: O(n)

---

1️⃣1️⃣ Comparison: Hamiltonian vs Euler Circuit

Feature	Hamiltonian Circuit	Euler Circuit
Focus	Vertices	Edges
Visit	Each vertex once	Each edge once
Complexity	NP-Complete	Polynomial
Condition	No simple rule	Degree-based rules

---

1️⃣2️⃣ Applications

• Traveling Salesman Problem (TSP)
• Routing and scheduling
• Circuit design
• Genome sequencing
• Network topology

---

1️⃣3️⃣ Advantages of Backtracking Approach

✔ Systematic exploration
✔ Prunes invalid paths early
✔ Easy to understand

---

1️⃣4️⃣ Limitations

✖ Very high time complexity
✖ Not suitable for large graphs

---

🔚 Conclusion

The Hamiltonian Circuit Problem is a fundamental problem that demonstrates the power and limitations of backtracking and highlights the challenges of NP-Complete problems.

Hamiltonian Circuit focuses on visiting all vertices exactly once in a closed loop.

---