Overview
In this article, we shall learn about Hamiltonian Paths. A Hamiltonian path in a graph is any path that visits every node exactly once, not less, not more.
Problem Statement
Given, an undirected graph ‘G’, in its adjacency matrix form, contains ‘n’ nodes. Determine whether or not G consists of any Hamiltonian paths.
Examples
G = {{0, 1, 1, 1, 0}, {1, 0, 1, 0, 1}, {1, 1, 0, 1, 1}, {1, 0, 1, 0, 0}}
Yes, G has a Hamiltonian Path, as shown in the image ahead:
Brute Force method
One simple solution is to produce every possible permutation of the n nodes. For every permutation, determine whether or not is it a valid hamiltonian path. This is done by checking if there exists an edge between adjacent nodes.
Time Complexity
O(N * N!)
Space Complexity
O(1)
An Efficient Alternative
We can use Dynamic-Programming and Bitmasking to optime the aforementioned brute force approach. For each subset ‘s’ of nodes, check if there’s a hamiltonian path in s ending at some node ‘v’ that is present in v. If there exists any node ‘u’ such that it is a neighbor to v, there also will exist a hamiltonian path ending at u. We solve the problem by generalizing the ending node of the Hamiltonian path and the subset of nodes.
Implementation
Output