Hamiltonian Cycle

The Hamiltonian cycle problem involves finding a cycle that visits each vertex in a graph exactly once. It models optimization problems like the traveling salesman problem.

Java example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
boolean hasHamiltonianCycle(int[][] graph) {
  int n = graph.length;
  int[] path = new int[n];

  return hamCycle(graph, 0, path, 0);
}

boolean hamCycle(int[][] graph, int currPos, int[] path, int count) {
  
  if (count == n-1) {
    return graph[currPos][path[0]] == 1; 
  }
  
  for (int i = 0; i < n; i++) {
    if (graph[currPos][i] == 1 && visited(i, path)) {  
      path[count] = i;
      if (hamCycle(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
23
24
bool hasHamiltonianCycle(vector<vector<int>> graph) {
  int n = graph.size();
  vector<int> path(n, -1);

  return hamCycle(graph, 0, path, 0); 
}

bool hamCycle(vector<vector<int>>& graph, int currPos, vector<int>& path, int count) {

  if (count == n-1) {
    return graph[currPos][path[0]];
  }

  for (int i = 0; i < n; i++) {
    if (graph[currPos][i] && !visited(path, i)) {
      path[count] = i;
      if (hamCycle(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_cycle(graph):
  
  n = len(graph)
  path = [-1] * n

  return ham_cycle(graph, 0, path, 0)
  
def ham_cycle(graph, curr_pos, path, count):

  if count == n-1:
    return graph[curr_pos][path[0]] == 1

  for i in range(n):
    if graph[curr_pos][i] and not visited(path, i):
      path[count] = i
      if ham_cycle(graph, i, path, count+1):
        return True
      path[count] = -1

  return False

Finding a Hamiltonian cycle is NP-Complete. Used for route optimization and sequencing problems.

A Hamiltonian cycle in a graph is a cycle that visits every vertex exactly once and returns to the original vertex. Determining whether such a cycle exists in a given graph is known as the Hamiltonian cycle problem, which is NP-complete. This concept is widely used in optimization problems, including the famous Traveling Salesman Problem.

Example Code in Java

 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
51
52
53
54
55
56
57
58
public class HamiltonianCycle {
    static int V = 5;
    int path[];

    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;
    }

    boolean hamCycleUtil(int graph[][], int path[], int pos) {
        if (pos == V) {
            return (graph[path[pos - 1]][path[0]] == 1);
        }

        for (int v = 1; v < V; v++) {
            if (isSafe(v, graph, path, pos)) {
                path[pos] = v;

                if (hamCycleUtil(graph, path, pos + 1) == true)
                    return true;

                path[pos] = -1;
            }
        }
        return false;
    }

    int hamCycle(int graph[][]) {
        path = new int[V];
        for (int i = 0; i < V; i++)
            path[i] = -1;

        path[0] = 0;
        if (hamCycleUtil(graph, path, 1) == false) {
            return 0;
        }

        return 1;
    }

    public static void main(String args[]) {
        HamiltonianCycle hamiltonian = new HamiltonianCycle();
        int graph1[][] = {{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 result = hamiltonian.hamCycle(graph1);
        System.out.println("Hamiltonian Cycle: " + (result == 1 ? "Exists" : "Doesn't Exist"));
    }
}

Example Code in 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <vector>
using namespace std;

const int V = 5;
vector<int> path(V, -1);

bool isSafe(int v, vector<vector<int>> &graph, 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 hamCycleUtil(vector<vector<int>> &graph, int pos) {
    if (pos == V) {
        return (graph[path[pos - 1]][path[0]] == 1);
    }

    for (int v = 1; v < V; ++v) {
        if (isSafe(v, graph, pos)) {
            path[pos] = v;
            if (hamCycleUtil(graph, pos + 1))
                return true;

            path[pos] = -1;
        }
    }
    return false;
}

bool hamCycle(vector<vector<int>> &graph) {
    path[0] = 0;
    return hamCycleUtil(graph, 1);
}

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}};

    cout << "Hamiltonian Cycle: " << (hamCycle(graph) ? "Exists" : "Doesn't Exist") << endl;
}

Example Code in Python

 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
def isSafe(v, graph, path, pos):
    if graph[path[pos - 1]][v] == 0:
        return False

    if v in path:
        return False

    return True

def hamCycleUtil(graph, path, pos):
    if pos == len(graph):
        return graph[path[pos - 1]][path[0]] == 1

    for v in range(1, len(graph)):
        if isSafe(v, graph, path, pos):
            path[pos] = v
            if hamCycleUtil(graph, path, pos + 1):
                return True
            path[pos] = -1

    return False

def hamCycle(graph):
    path = [-1] * len(graph)
    path[0] = 0

    if hamCycleUtil(graph, path, 1):
        return True

    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]]

print("Hamiltonian Cycle:", "Exists" if hamCycle(graph) else "Doesn't Exist")

Each of these example codes attempts to find a Hamiltonian cycle in a given graph using a backtracking method. If a Hamiltonian cycle exists, the code will print “Exists”, otherwise “Doesn’t Exist”.