What is the use of the Hamiltonian cycle?

It is used in computer graphics, electronic circuit design, and many more. A real-life application of the Hamiltonian cycle includes genome mapping. Another example includes framing a bus route for school students. Here nodes = students, edges = paths to be traveled and all paths are to be traversed only once.

What is a cycle in graph theory?

A cycle includes no repetition of vertices except the first and the last vertices. A graph with a cycle is termed a cyclic graph. A cycle is also called a simple circuit.

What is an undirected graph?

In these graphs, the edge does not have any directions. It is used only to detect if any relationship exists between two vertices. The topology we use in computers to connect them is the concept of undirected graphs.

Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample example

Approach

2.1.

PseudoCode

Implementation in C++

3.1.

Complexity Analysis

FAQs

Key Takeaways

Last Updated: Mar 27, 2024

Print all Hamiltonian Cycles in an Undirected Graph.

Author Urwashi Priya

Do you think IIT Guwahati certified course can help you in your career?

Yes

Introduction

In this blog, we will be discussing a backtracking problem that has been asked frequently in Interviews.
The problem is to Print all Hamiltonian Cycles in an Undirected Graph.

Before we proceed, we must understand what do we mean by backtracking and hamiltonian cycles in a graph?

Backtracking: Backtracking is an algorithmic technique that is used for solving the problem based on recursion by building each and every possible solution incrementally and removing those answers that fail to satisfy the problem’s constraints at any time.

Let us recall what is a hamiltonian cycle?
Hamiltonian cycle: Taking any source vertex, we have to visit all the vertices exactly once and reach back to the starting vertex without repeating any vertices.

Now let’s look at the problem.

Problem Statement

We are given an undirected graph consisting of N nodes. This graph is represented in the form of an adjacency matrix of size N X N. Our work is to print all possible hamiltonian cycles.

Sample example

The given graph is represented as:

Adjacency matrix representation of the given graph

{ 0, 1, 1, 0, 0, 1 }
{ 1, 0, 1, 0, 1, 1 }
{ 1, 1, 0, 1, 0, 0 }
{ 0, 0, 1, 0, 1, 0 }
{ 0, 1, 0, 1, 0, 1 }
{ 1, 1, 0, 0, 1, 0 }

Output:

0 1 2 3 4 5 0 
0 1 5 4 3 2 0 
0 2 3 4 1 5 0 
0 2 3 4 5 1 0 
0 5 1 4 3 2 0 
0 5 4 3 2 1 0

Explanation for the output:

On traversing the graph in the order 0->1->2->3->4->5->0, we can see that by traversing each and every vertex exactly once, we can reach our source (here 0). We can repeat the same by different paths also as depicted in our output.

Approach

Now to Print all Hamiltonian Cycles in an Undirected Graph, the following approach is followed.

First, we will define a function that will check if the vertex being considered at present is not adjacent to the previous vertex and is not already included in the path.

If the above two conditions hold, the vertex is safe to be counted.

⬇

Next, we will define a function to find all hamiltonian cycles. All vertices of the graph will be included here, and a path must exist from the last vertex to the starting vertex.

⬇

We will include the source vertex in our path and print the entire path. After printing the path, we have to remove the source vertex added.

⬇

The above steps have to be repeated for the following vertices to find a different path.

⬇

All possible hamiltonian cycles will be printed. If the conditions above are not satisfied, we will mention that no hamiltonian cycles are possible.

This is our most optimised approach using backtracking. It will take O(N!) time.
Till now, I assume you have got the basic and conceptual idea of what has been mentioned in the problem statement. So, I recommend you first give it a try. Coding Ninjas Studio

If you were unable to solve it, don’t be disappointed.

Please have a thorough look over the algorithm(pseudocode), and then again, you must try solving it.

PseudoCode

To Print all Hamiltonian Cycles in an Undirected Graph:

___________________________________________________________________

procedure isSafe(int v, int graph[][6], vector<int> path, int pos):

___________________________________________________________________

1. If graph[path[pos - 1]][v] == 0:

return false

2. for ( i = 0 to pos)

if (path[i] == v): return false;

3. return true

4. end procedure

___________________________________________________________________

procedure FindHamCycle(int graph[][6], int pos, vector<int> path, bool visited[], int N):

___________________________________________________________________

1. if (pos == N):

if (graph[path[path.size() - 1]][path[0]] != 0):

path.push_back(0)

for (i = 0 to path.size()):

cout << path[I] << " "

path.pop_back()

hasCycle = true

return

2. for ( v = 0 to N):

if (isSafe(v, graph, path, pos) && !visited[v]):

path.push_back(v)

visited[v] = true

FindHamCycle(graph, pos + 1, path, visited, N)

visited[v] = false;

path.pop_back()

3. end procedure

___________________________________________________________________

procedure hamCycle(int graph[][6], int N):

___________________________________________________________________

1. hasCycle = false

2. vector<int> path

3. path.push_back(0)

4. bool visited[N]

5. for(i=0 to N):

visited[i] = false

6. visited[0] = true

7. FindHamCycle(graph, 1, path, visited, N)

8. if (!hasCycle): cout << "No Hamiltonian Cycle" << "possible " << endl

9. end procedure

___________________________________________________________________

Implementation in C++

// C++ program to Print all Hamiltonian Cycles in an Undirected Graph
#include <bits/stdc++.h>
using namespace std;

bool hasCycle;
bool isSafe(int v, int graph[][6], vector<int> path, int pos)
{
    // If the new vertex is adjacent to the previous vertex
    if (graph[path[pos - 1]][v] == 0)
        return false;

    // If the new vertex is already included in the path
    for (int i = 0; i < pos; i++)
        if (path[i] == v)
            return false;

    return true;
}

void FindHamCycle(int graph[][6], int pos, vector<int> path, bool visited[], int N)
{
    // If all vertices traversed in Hamiltonian Cycle
    if (pos == N)
    {

        // If there exists an edge from the last vertex to the first vertex
        if (graph[path[path.size() - 1]][path[0]] != 0)
        {

            // path will include source vertex and then print the entire path traversed
            path.push_back(0);
            // printing the path
            for (int i = 0; i < path.size(); i++)
            {
                cout << path[i] << " ";
            }
            cout << endl;

            // Removing the source vertex added first
            path.pop_back();

            // Updating the hasCycle variable
            hasCycle = true;
        }
        return;
    }

    // repeat for different vertices

    for (int v = 0; v < N; v++)
    {

        // Checking if this vertex is safe to be added to the Cycle being traversed
        if (isSafe(v, graph, path, pos) && !visited[v])
        {

            path.push_back(v);
            visited[v] = true;

            // using recursion to frame rest of the way
            FindHamCycle(graph, pos + 1, path, visited, N);

            // Removing current vertex from path and process other vertices
            visited[v] = false;
            path.pop_back();
        }
    }
}

void hamCycle(int graph[][6], int N)
{

    hasCycle = false;
    vector<int> path;
    path.push_back(0);

    // Keeps the track of the visited vertices
    bool visited[N];

    for (int i = 0; i < N; i++)
        visited[i] = false;

    visited[0] = true;

    FindHamCycle(graph, 1, path, visited, N);

    if (!hasCycle)
    {

        // If no Hamiltonian Cycle is possible

        cout << "No Hamiltonian Cycle"
             << "possible " << endl;
        return;
    }
}

int main()
{
    int graph[][6] = {
        {0, 1, 1, 0, 0, 1},
        {1, 0, 1, 0, 1, 1},
        {1, 1, 0, 1, 0, 0},
        {0, 0, 1, 0, 1, 0},
        {0, 1, 0, 1, 0, 1},
        {1, 1, 0, 0, 1, 0},
    };
    hamCycle(graph, 6);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

0 1 2 3 4 5 0 
0 1 5 4 3 2 0 
0 2 3 4 1 5 0 
0 2 3 4 5 1 0 
0 5 1 4 3 2 0 
0 5 4 3 2 1 0

Complexity Analysis

Time Complexity: O(N!).

Analysing Time Complexity: The matrix is traversed N! times, where N is the number of nodes in the graph.

Space complexity: O(N).as the space required to print the paths will take N space where N is the number of nodes in the graph.

You can also read Detect cycle in an undirected graph here.

FAQs

What is the use of the Hamiltonian cycle?
It is used in computer graphics, electronic circuit design, and many more. A real-life application of the Hamiltonian cycle includes genome mapping. Another example includes framing a bus route for school students. Here nodes = students, edges = paths to be traveled and all paths are to be traversed only once.
What is a cycle in graph theory?
A cycle includes no repetition of vertices except the first and the last vertices. A graph with a cycle is termed a cyclic graph. A cycle is also called a simple circuit.
What is an undirected graph?
In these graphs, the edge does not have any directions. It is used only to detect if any relationship exists between two vertices. The topology we use in computers to connect them is the concept of undirected graphs.

Key Takeaways

This article taught us to Print all Hamiltonian Cycles in an Undirected Graph by approaching this problem using backtracking. We have discussed its implementation using illustrations, pseudocode and then our optimised code.

We hope you could easily take away all critical techniques like analysing problems by walking over the execution of the examples and finding out the recursive pattern followed in most backtracking problems.

Check out this problem - Root To Leaf Path

Now, we recommend you practice problem sets based on backtracking to master your fundamentals. You can get a wide range of questions similar to this problem on Coding Ninjas Studio.
It's not the end. Must solve the problem of similar types.

Happy Coding.