Hamiltonian Graph - Naukri Code 360

Introduction

A Hamiltonian graph is a unique type of graph in both mathematics and computer science. It features a cycle that passes through every vertex exactly once and then returns to the starting vertex. Understanding Hamiltonian graphs is crucial for addressing problems in areas like routing, task scheduling, and designing efficient network structures.

In this article, you will learn about Hamiltonian graphs, their properties, and how to implement algorithms to find Hamiltonian cycles using different programming languages.

What is a Hamiltonian Graph?

A Hamiltonian graph is a graph that contains a Hamiltonian cycle, which is a closed loop passing through each vertex exactly once before returning to the starting point. A graph is considered Hamiltonian if it has this cycle. However, not all graphs have Hamiltonian cycles, and identifying them can be challenging. The Hamiltonian Path Problem focuses on finding a path that visits every vertex exactly once, without requiring a return to the starting point, making it distinct from the Hamiltonian cycle.

Example of Hamiltonian Graph

Consider a simple graph with vertices A, B, C, and D, connected as follows:

A -- B
  |    |
  D -- C

In this graph, one Hamiltonian cycle is A → B → C → D → A. Each vertex is visited once, and the cycle returns to the starting point.

Problem Statement

Finding Hamiltonian cycles is classified as an NP-complete problem, which means there is no known efficient algorithm to solve every instance of the problem. This complexity highlights the need for algorithms designed to tackle specific cases effectively. The problem is defined as: Given a graph, determine whether it contains a Hamiltonian cycle, a loop that visits each vertex exactly once before returning to the starting point.

Illustrations

Let's see how the backtracking algorithm works to find a Hamiltonian cycle in an example graph. Consider the following undirected graph with 4 vertices:

   B -- C
  / \  /
 A---D

We start at vertex A and recursively explore all possible paths:

1. Path: [A]

Unvisited neighbors: B, D

Choose B, Path: [A, B]

2. Path: [A, B]

Unvisited neighbors: C, D

Choose C, Path: [A, B, C]

3. Path: [A, B, C]

Unvisited neighbors: D

Choose D, Path: [A, B, C, D]

4. Path: [A, B, C, D]

All vertices visited & last vertex D has an edge to starting vertex A

Hamiltonian cycle found: [A, B, C, D, A]

In this example, the algorithm finds the Hamiltonian cycle [A, B, C, D, A]. If we had chosen a different sequence of vertices, like [A, D, C, B], it would have also led to a valid Hamiltonian cycle.

Now let's look at another example where the graph does not have a Hamiltonian cycle:

   B---C
  / 
 A---D

1. Path: [A]

Unvisited neighbors: B, D

Choose B, Path: [A, B]

2. Path: [A, B]

Unvisited neighbors: C

Choose C, Path: [A, B, C]

3. Path: [A, B, C]

Unvisited neighbors: D

Choose D, Path: [A, B, C, D]

4. Path: [A, B, C, D]

All vertices visited but last vertex D does not have an edge to starting vertex A

Backtrack & remove D from path

5. Path: [A, B, C]

No more unvisited neighbors

Backtrack & remove C from path

6. Path: [A, B]

No more unvisited neighbors

Backtrack & remove B from path

7. Path: [A]

Choose D, Path: [A, D]

8. Path: [A, D]

No unvisited neighbors that can lead to a Hamiltonian cycle

Backtrack & remove D from path

9. Path: [A]

No more unvisited neighbors

No Hamiltonian cycle found

In this case, the algorithm explores all possible paths but does not find a Hamiltonian cycle because one does not exist in the graph.

Hamiltonian Cycle using Backtracking Algorithm

Backtracking is an approach used to solve problems step by step by trying out partial solutions and discarding those that do not meet the problem's requirements. When applying backtracking to find a Hamiltonian cycle, the algorithm explores all potential paths in the graph and eliminates paths that do not form a valid cycle, ensuring that each vertex is visited exactly once.

Backtracking Implementation in Various Languages

C

#include <stdio.h>
#include <stdbool.h>

#define V 5

bool isSafe(int graph[V][V], int path[], int pos, int v) {
    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 hamiltonianCycleUtil(int graph[V][V], int path[], int pos) {
    if (pos == V) {
        return graph[path[pos - 1]][path[0]] == 1;
    }
    for (int v = 1; v < V; v++) {
        if (isSafe(graph, path, pos, v)) {
            path[pos] = v;
            if (hamiltonianCycleUtil(graph, path, pos + 1)) return true;
            path[pos] = -1;
        }
    }
    return false;
}

bool hamiltonianCycle(int graph[V][V]) {
    int path[V];
    for (int i = 0; i < V; i++) path[i] = -1;
    path[0] = 0;
    return hamiltonianCycleUtil(graph, path, 1);
}

int main() {
    int graph[V][V] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 1, 0},
        {0, 1, 0, 0, 1},
        {1, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
    };
    if (hamiltonianCycle(graph)) {
        printf("Graph has a Hamiltonian Cycle\n");
    } else {
        printf("Graph does not have a Hamiltonian Cycle\n");
    }
    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
#include <vector>
using namespace std;

#define V 5

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

bool hamiltonianCycle(int graph[V][V]) {
    vector<int> path(V, -1);
    path[0] = 0;
    return hamiltonianCycleUtil(graph, path, 1);
}

int main() {
    int graph[V][V] = {
        {0, 1, 0, 1, 0},
        {1, 0, 1, 1, 0},
        {0, 1, 0, 0, 1},
        {1, 1, 0, 0, 1},
        {0, 0, 1, 1, 0}
    };
    if (hamiltonianCycle(graph)) {
        cout << "Graph has a Hamiltonian Cycle" << endl;
    } else {
        cout << "Graph does not have a Hamiltonian Cycle" << endl;
    }
    return 0;
}

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

Run Code

Java

import java.util.Arrays;

public class HamiltonianCycle {
    static final int V = 5;

    static boolean isSafe(int graph[][], int path[], int pos, int v) {
        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 hamiltonianCycleUtil(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(graph, path, pos, v)) {
                path[pos] = v;
                if (hamiltonianCycleUtil(graph, path, pos + 1)) return true;
                path[pos] = -1;
            }
        }
        return false;
    }

    static boolean hamiltonianCycle(int graph[][]) {
        int path[] = new int[V];
        Arrays.fill(path, -1);
        path[0] = 0;
        return hamiltonianCycleUtil(graph, path, 1);
    }

    public static void main(String[] args) {
        int graph[][] = {
            {0, 1, 0, 1, 0},
            {1, 0, 1, 1, 0},
            {0, 1, 0, 0, 1},
            {1, 1, 0, 0, 1},
            {0, 0, 1, 1, 0}
        };
        if (hamiltonianCycle(graph)) {
            System.out.println("Graph has a Hamiltonian Cycle");
        } else {
            System.out.println("Graph does not have a Hamiltonian Cycle");
        }
    }
}

You can also try this code with Online Java Compiler

Run Code

JavaScript

const V = 5;

function isSafe(graph, path, pos, v) {
    if (graph[path[pos - 1]][v] === 0) return false;
    for (let i = 0; i < pos; i++)
        if (path[i] === v) return false;
    return true;
}

function hamiltonianCycleUtil(graph, path, pos) {
    if (pos === V) {
        return graph[path[pos - 1]][path[0]] === 1;
    }
    for (let v = 1; v < V; v++) {
        if (isSafe(graph, path, pos, v)) {
            path[pos] = v;
            if (hamiltonianCycleUtil(graph, path, pos + 1)) return true;
            path[pos] = -1;
        }
    }
    return false;
}

function hamiltonianCycle(graph) {
    let path = Array(V).fill(-1);
    path[0] = 0;
    return hamiltonianCycleUtil(graph, path, 1);
}

const graph = [
    [0, 1, 0, 1, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [1, 1, 0, 0, 1],
    [0, 0, 1, 1, 0]
];

if (hamiltonianCycle(graph)) {
    console.log("Graph has a Hamiltonian Cycle");
} else {
    console.log("Graph does not have a Hamiltonian Cycle");
}

You can also try this code with Online Javascript Compiler

Run Code

Python


V = 5

def isSafe(graph, path, pos, v):
    if graph[path[pos - 1]][v] == 0:
        return False
    for i in range(pos):
        if path[i] == v:
            return False
    return True

def hamiltonianCycleUtil(graph, path, pos):
    if pos == V:
        return graph[path[pos - 1]][path[0]] == 1
    for v in range(1, V):
        if isSafe(graph, path, pos, v):
            path[pos] = v
            if hamiltonianCycleUtil(graph, path, pos + 1):
                return True
            path[pos] = -1
    return False

def hamiltonianCycle(graph):
    path = [-1] * V
    path[0] = 0
    return hamiltonianCycleUtil(graph, path, 1)

graph = [
    [0, 1, 0, 1, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [1, 1, 0, 0, 1],
    [0, 0, 1, 1, 0]
]

if hamiltonianCycle(graph):
    print("Graph has a Hamiltonian Cycle")
else:
    print("Graph does not have a Hamiltonian Cycle")

You can also try this code with Online Python Compiler

Run Code

PHP

<?php
define('V', 5);

function isSafe($graph, $path, $pos, $v) {
    if ($graph[$path[$pos - 1]][$v] == 0) return false;
    for ($i = 0; $i < $pos; $i++)
        if ($path[$i] == $v) return false;
    return true;
}

function hamiltonianCycleUtil($graph, $path, $pos) {
    if ($pos == V) {
        return $graph[$path[$pos - 1]][$path[0]] == 1;
    }
    for ($v = 1; $v < V; $v++) {
        if (isSafe($graph, $path, $pos, $v)) {
            $path[$pos] = $v;
            if (hamiltonianCycleUtil($graph, $path, $pos + 1)) return true;
            $path[$pos] = -1;
        }
    }
    return false;
}

function hamiltonianCycle($graph) {
    $path = array_fill(0, V, -1);
    $path[0] = 0;
    return hamiltonianCycleUtil($graph, $path, 1);
}

$graph = [
    [0, 1, 0, 1, 0],
    [1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1],
    [1, 1, 0, 0, 1],
    [0, 0, 1, 1, 0]
];

if (hamiltonianCycle($graph)) {
    echo "Graph has a Hamiltonian Cycle\n";
} else {
    echo "Graph does not have a Hamiltonian Cycle\n";
}
?>

You can also try this code with Online PHP Compiler

Run Code

Output

Graph has a Hamiltonian Cycle

Time Complexity

The time complexity of using a backtracking algorithm to find Hamiltonian cycles is O(N!), where N represents the number of vertices in the graph. This is because we have to explore all potential paths.

Space Complexity

The space complexity is O(N) due to the need to store the path array.

Applications of Hamiltonian Graphs

Hamiltonian graphs have several uses in various fields:

Routing Problems: They help in designing efficient routes for delivery and logistics services.
Scheduling: They assist in scheduling tasks in computer systems.
Genetics: They are useful in analyzing genetic sequences and their pathways.
Network Design: They help in creating network topologies that ensure efficient connectivity.

Frequently Asked Questions

What is a Hamiltonian graph?

A Hamiltonian graph is one that has a cycle visiting every vertex exactly once and returns to the starting point.

Why is the Hamiltonian cycle problem important?

This problem is crucial because of its applications in routing, scheduling, and network design.

What is the time complexity of finding Hamiltonian cycles?

The time complexity is O(N!), where N is the number of vertices, due to exploring all possible paths.

Conclusion

In this article, we covered Hamiltonian graphs and their main characteristics. A Hamiltonian graph contains a cycle that visits each vertex once and returns to the start. We also discussed how to find Hamiltonian cycles using the backtracking algorithm, with examples in different programming languages. Hamiltonian graphs are vital for solving practical problems in areas such as logistics, scheduling, and network design.

You can also check out our other blogs on Code360.