Hamiltonian Path Problem

Problem Statement:

Given an undirected graph. The task is to print all the Hamiltonian cycles present in the graph.

A Hamiltonian Cycle is a cycle that traverses all the nodes of the graph exactly once and returns back to the starting point.

Example :

Input :

Approach: Backtracking

The problem can be solved using a backtracking approach. Follow the below steps to solve the problem.

Algorithm:

• Create an empty path array.
• Add the vertex 0 to the array.
• Start adding vertex 1 and other connected nodes and check if the current vertex can be included in the array or not.
• This can be done by using a visiting array and checking if the vertex has already been visited or is adjacent to the previously added vertex.
• If any such vertex is found, add it to the array and backtrack from that node.
• Try every possible combination and if a path returns false, ignore the vertex and start iterating from the next vertex till all the nodes have been visited.

Implementation of the Approach:

C++ Code

#define N 8
//vertices
char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
//adjacency matrix
int adjacencyM[N][N]= {{0, 1, 0, 0, 0, 0, 0, 1},
                       {1, 0, 1, 0, 0, 0, 0, 0},
                       {0, 1, 0, 1, 0, 0, 0, 1},
                       {0, 0, 1, 0, 1, 0, 1, 0},
                       {0, 0, 0, 1, 0, 1, 0, 0},
                       {0, 0, 0, 0, 1, 0, 1, 0},
                       {0, 0, 0, 1, 0, 1, 0, 1},
                       {1, 0, 1, 0, 0, 0, 1, 0}};
 
//list mapping of vertices to mark vertex visited
int visited[N] {
  0
};
 
class Hamiltonian {
  public:
    //start (& end) vertex
    int start;
  //stack used as list to store the path of the cycle
  list < int > cycle;
  //variable to mark if graph has the cycle
  bool hasCycle = false;
//constructor
  Hamiltonian(int start) {
    this -> start = start;
  }
 
  //method to initiate the search of the Hamiltonian cycle
  void findCycle() {
    //add starting vertex to the list
    cycle.push_back(start);
 
    //start searching the path
    solve(start);
  }
 
  void solve(int vertex) {
    //Base condition: if the vertex is the start vertex
    //and all nodes have been visited (start vertex twice)
    if (vertex == start && cycle.size() == N + 1) {
      hasCycle = true;
 
      //output the cycle
      displayCycle();
 
      //return to explore more hamiltonian cycles
      return;
    }
 
    //iterate through the neighbor vertices
    for (int i = 0; i < N; i++) {
      if (adjacencyM[vertex][i] == 1 && visited[i] == 0) {
        int nbr = i;
        //visit and add vertex to the cycle
        visited[nbr] = 1;
        cycle.push_back(nbr);
 
        //Go to the neighbor vertex to find the cycle
        solve(nbr);
   //Backtrack
        visited[nbr] = 0;
        cycle.pop_back();
      }
    }
  }
 
  //Function to display hamiltonian cycle
  void displayCycle() {
    cout << "[";
    for (int v: cycle) {
      cout << vertices[v] << " ";
    }
    cout << "] \n";
  }
};

Java Code

 class Hamiltonian {
  //vertices
  char vertices[];
  //adjacency matrix
  int adjacencyM[][];
  //list mapping of vertices to mark vertex visited
  int visited[];
  //start (& end) vertex index
  int start;
  //stack used as list to store the path of the cycle
  Stack < Integer > cycle = new Stack < > ();
  //number of vertices in the graph
  int N;
  //variable to mark if graph has the cycle
  boolean hasCycle = false;
 
  //constructor
  Hamiltonian(int start, char vertices[], int adjacencyM[][]) {
    this.start = start;
    this.vertices = vertices;
    this.adjacencyM = adjacencyM;
    this.N = vertices.length;
    this.visited = new int[vertices.length];
  }
 
  //method to initiate the search of the Hamiltonian cycle
  public void findCycle() {
    //add starting vertex to the list
    cycle.push(start);
 
    //start searching the path
    solve(start);
  }
 
  private void solve(int vertex) {
    //Base condition: if the vertex is the start vertex
    //and all nodes have been visited (start vertex twice)
    if (vertex == start && cycle.size() == N + 1) {
      hasCycle = true;
 
      //output the cycle
      displayCycle();
 
      //return to explore more hamiltonian cycles
      return;
    }
 
    //iterate through the neighbor vertices
    for (int i = 0; i < N; i++) {
      if (adjacencyM[vertex][i] == 1 && visited[i] == 0) {
        int nbr = i;
        //visit and add vertex to the cycle
        visited[nbr] = 1;
        cycle.push(nbr);
 
        //Go to the neighbor vertex to find the cycle
        solve(nbr);
 
        //Backtrack
        visited[nbr] = 0;
    cycle.pop();
      }
    }
  }
 
  //Method to display the path of the cycle
  void displayCycle() {
    //converting vertex index to the name
    List < Character > names = new ArrayList < > ();
    for (int idx: cycle) {
      names.add(vertices[idx]);
    }
    System.out.println(names);
  }
}
class Main {
  public static void main(String[] args) {
    //vertices
    char vertices[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    //adjacency matrix
    int adjacencyM[][]= {{0, 1, 0, 0, 0, 0, 0, 1},
                         {1, 0, 1, 0, 0, 0, 0, 0},
                         {0, 1, 0, 1, 0, 0, 0, 1},
                         {0, 0, 1, 0, 1, 0, 1, 0},
                         {0, 0, 0, 1, 0, 1, 0, 0},
                         {0, 0, 0, 0, 1, 0, 1, 0},
                         {0, 0, 0, 1, 0, 1, 0, 1},
                         {1, 0, 1, 0, 0, 0, 1, 0}};
 
    //Driver code
    Hamiltonian hamiltonian = new Hamiltonian(0,vertices, adjacencyM);
    hamiltonian.findCycle();
 
    //if the graph doesn't have any Hamiltonian Cycle
    if(!hamiltonian.hasCycle){
      System.out.println("No Hamiltonian Cycle");
    }
  }
}

Python Code

class Hamiltonian:
    def __init__(self, start):
        # start (& end) vertex
        self.start = start
 
        # list to store the cycle path
        self.cycle = []
 
        # variable to mark if graph has the cycle
        self.hasCycle = False
 
    # method to initiate the search of cycle
    def findCycle(self):
        # add starting vertex to the list
        self.cycle.append(self.start)
 
        # start the search of the hamiltonian cycle
        self.solve(self.start)
 
    # recursive function to implement backtracking
    def solve(self, vertex):
        # Base condition: if the vertex is the start vertex
        # and all nodes have been visited (start vertex twice)
        if vertex == self.start and len(self.cycle) == N + 1:
            self.hasCycle = True
 
            # output the cycle
            self.displayCycle()
 
            # return to explore more cycles
            return
 
        # iterate through the neighbor vertices
        for i in range(len(vertices)):
            if adjacencyM[vertex][i] == 1 and visited[i] == 0:
                nbr = i
 # visit and add vertex to the cycle
                visited[nbr] = 1
                self.cycle.append(nbr)
 
                # traverse the neighbor vertex to find the cycle
                self.solve(nbr)
 
                # Backtrack
                visited[nbr] = 0
                self.cycle.pop()
 
    # function to display the hamiltonian class
    def displayCycle(self):
        names = []
        for v in self.cycle:
            names.append(vertices[v])
        print(names)
 
if __name__ == '__main__':
  vertices = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
  adjacencyM = [[0, 1, 0, 0, 0, 0, 0, 1],
                [1, 0, 1, 0, 0, 0, 0, 0],
                [0, 1, 0, 1, 0, 0, 0, 1],
                [0, 0, 1, 0, 1, 0, 1, 0],
                [0, 0, 0, 1, 0, 1, 0, 0],
                [0, 0, 0, 0, 1, 0, 1, 0],
                [0, 0, 0, 1, 0, 1, 0, 1],
                [1, 0, 1, 0, 0, 0, 1, 0]]
  #list mapping of vertices to mark vertex visited
  visited = [0 for x in range(len(vertices))]
 
  #number of vertices in the graph
  N = 8
 
  #Driver code
  hamiltonian = Hamiltonian(0)
  hamiltonian.findCycle()
 
  #if the graph doesn't have any Hamiltonian Cycle
  if not hamiltonian.hasCycle:
 print("No Hamiltonian Cycle")

• Time Complexity: O(N!), where N is the number of vertices.
• Space Complexity: O(1), as no extra space is used.

Practice Questions:

• Cycle in Undirected Graph

FAQ

Q.1: What is the time and space complexity of the backtracking approach?

Ans: The time and space complexity of the backtracking approach. is O(N!) and O(1), where N is the number of vertices.

Q.2: What is a Hamiltonian Cycle?

Ans: A Hamiltonian Cycle is a cycle that traverses all the nodes of the graph exactly once and returns back to the starting point.