Visualizing Hamiltonian Circuit with Python: A Backtracking Approach

In this video, we demonstrate our implementation of the Hamiltonian Circuit Problem using the Backtracking Algorithm as part of the "Design and Analysis of Algorithms"

A Hamiltonian Circuit is a path in a graph that visits every vertex exactly once and returns to the starting vertex. We represent the graph structures using Adjacency Matrices and utilize Python to build and visualize the solution.

Team Members:
Kadek Wahyu Ardia Putra (2415101002)
I Gede Indra Pandika (2415101012)
Danvi Almasrazqi Suwatno (2415101055)

What we cover in this video:

1. Graph Representation: How we use adjacency matrices to define node relationships.
2. Backtracking Process: A step-by-step explanation of how the algorithm searches for a valid path and prunes invalid branches.
3. Code Walkthrough: Exploring our Python code, including the `is_valid()` function and recursive backtracking logic.
4. Analysis Questions: Answering key questions about the difference between Hamiltonian Paths and Circuits, and the efficiency of the backtracking approach.

Tools Used:
Python
NetworkX & Matplotlib (for Graph Visualization)

Видео Visualizing Hamiltonian Circuit with Python: A Backtracking Approach канала Kadek Wahyu Ardia Putra