Hamiltonian Path
The Hamiltonian path problem involves finding a path that visits each vertex in a graph exactly once. It models optimization problems like the traveling salesman path.
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| boolean hasHamiltonianPath(int[][] graph) {
int n = graph.length;
int[] path = new int[n];
return hamPath(graph, 0, path, 0);
}
boolean hamPath(int[][] graph, int currPos, int[] path, int count) {
if (count == n-1) return true;
for (int i = 0; i < n; i++) {
if (graph[currPos][i] == 1 && visited(i, path)) {
path[count] = i;
if (hamPath(graph, i, path, count+1)) {
return true;
}
path[count] = -1;
}
}
return false;
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| bool hasHamiltonianPath(vector<vector<int>> graph) {
int n = graph.size();
vector<int> path(n, -1);
return hamPath(graph, 0, path, 0);
}
bool hamPath(vector<vector<int>>& graph, int currPos, vector<int>& path, int count) {
if (count == n-1) return true;
for (int i = 0; i < n; i++) {
if (graph[currPos][i] && !visited(path, i)) {
path[count] = i;
if (hamPath(graph, i, path, count+1)) {
return true;
}
path[count] = -1;
}
}
return false;
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| def has_hamiltonian_path(graph):
n = len(graph)
path = [-1] * n
return ham_path(graph, 0, path, 0)
def ham_path(graph, curr_pos, path, count):
if count == n-1:
return True
for i in range(n):
if graph[curr_pos][i] and not visited(path, i):
path[count] = i
if ham_path(graph, i, path, count+1):
return True
path[count] = -1
return False
|
Finding a Hamiltonian path is NP-Complete. Used for sequencing and route planning problems.
A Hamiltonian path in a graph is a path that visits every vertex exactly once. Unlike an Eulerian path, which focuses on covering all edges, a Hamiltonian path covers all vertices without repetition. This concept is often used in optimization problems like the Traveling Salesman Problem.
Example Code in Java
Here is a simple Java code to find a Hamiltonian path in a graph using backtracking.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| public class HamiltonianPath {
static boolean isSafe(int v, int[][] graph, int[] path, int pos) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
static boolean hamiltonianPathUtil(int[][] graph, int[] path, int pos) {
if (pos == graph.length) {
return true;
}
for (int v = 1; v < graph.length; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamiltonianPathUtil(graph, path, pos + 1))
return true;
path[pos] = -1;
}
}
return false;
}
public static void main(String[] args) {
int[][] graph = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
int[] path = new int[graph.length];
path[0] = 0;
if (hamiltonianPathUtil(graph, path, 1))
for (int v : path) System.out.print(v + " ");
else
System.out.println("No Hamiltonian Path exists");
}
}
|
Example Code in C++
In C++, the algorithm remains the same. We use backtracking to find the Hamiltonian path.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <iostream>
#include <vector>
using namespace std;
bool isSafe(int v, vector<vector<int>> &graph, vector<int> &path, int pos) {
if (graph[path[pos - 1]][v] == 0)
return false;
for (int i = 0; i < pos; i++)
if (path[i] == v)
return false;
return true;
}
bool hamiltonianPathUtil(vector<vector<int>> &graph, vector<int> &path, int pos) {
if (pos == graph.size()) {
return true;
}
for (int v = 1; v < graph.size(); v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamiltonianPathUtil(graph, path, pos + 1))
return true;
path[pos] = -1;
}
}
return false;
}
int main() {
vector<vector<int>> graph = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
vector<int> path(graph.size(), -1);
path[0] = 0;
if (hamiltonianPathUtil(graph, path, 1)) {
for (int v : path) cout << v << " ";
} else {
cout << "No Hamiltonian Path exists";
}
return 0;
}
|
Example Code in Python
Python code for the Hamiltonian path is straightforward and similar to Java and C++.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| def is_safe(v, graph, path, pos):
if graph[path[pos - 1]][v] == 0:
return False
if v in path:
return False
return True
def hamiltonian_path_util(graph, path, pos):
if pos == len(graph):
return True
for v in range(1, len(graph)):
if is_safe(v, graph, path, pos):
path[pos] = v
if hamiltonian_path_util(graph, path, pos + 1):
return True
path[pos] = -1
return False
graph = [
[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0]
]
path = [-1] * len(graph)
path[0] = 0
if hamiltonian_path_util(graph, path, 1):
print(" ".join(map(str, path)))
else:
print("No Hamiltonian Path exists")
|
This shows you how to find a Hamiltonian path using backtracking in Java, C++, and Python.
Hamiltonian Path vs Hamiltonian Cycle
A Hamiltonian Path visits every vertex in a graph exactly once, but it doesn’t need to return to the starting vertex. A Hamiltonian Cycle, on the other hand, is a Hamiltonian Path that is a cycle, meaning it returns to the starting vertex after visiting all other vertices exactly once.
In simpler terms:
- Hamiltonian Path: Visits all vertices once.
- Hamiltonian Cycle: Visits all vertices once and returns to the start.
Finding a Hamiltonian Cycle in a graph is only a small step away from finding a Hamiltonian Path. If a Hamiltonian Path exists and there’s an edge between the last vertex in the path and the starting vertex, you can form a Hamiltonian Cycle.
For example, if you’ve found a Hamiltonian Path 0 -> 1 -> 2 -> 3 -> 4, and if there’s an edge from vertex 4 back to vertex 0, then you have a Hamiltonian Cycle 0 -> 1 -> 2 -> 3 -> 4 -> 0.