数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Hamiltonian Cycle

What is a Hamiltonian Cycle?

A Hamiltonian Cycle or Circuit is a path in a graph that visits every vertex exactly once and returns to the starting vertex, forming a closed loop. A graph is said to be a Hamiltonian graph only when it contains a hamiltonian cycle, otherwise, it is called non-Hamiltonian graph.

A graph is an abstract data type (ADT) consisting of a set of objects that are connected via links.

The practical applications of hamiltonian cycle problem can be seen in the fields like network design, delivery systems and many more. However, the solution to this problem can be found only for small types of graphs, and not for larger ones.

Input Output Scenario

Suppose the given undirected graph G(V, E) and its adjacency matrix are as follows −

Hamiltonian Cycle

The backtracking algorithm can be used to find a Hamiltonian path in the above graph. If found, the algorithm returns the path. If not, it returns false. For this case, the output should be (0, 1, 2, 4, 3, 0).

Finding Hamiltonian Cycle using Backtracking Approach

The naive way to solve Hamiltonian cycle problem is by generating all possible configurations of vertices and checking if any configuration satisfies the given constraints. However, this approach is not suitable for large graphs as its time complexity will be (O(N!)).

The following steps explain the working of backtracking approach −

  • First, create an empty path array and add a starting vertex 0 to it.

  • Next, start with vertex 1 and then add other vertices one by one.

  • While adding vertices, check whether a given vertex is adjacent to the previously added vertex and hasn't been added already.

  • If any such vertex is found, add it to the path as part of the solution, otherwise, return false.

Example

The following example demonstrates how to find a hamiltonian cycle within a given undirected graph.

#include <stdio.h>
#define NODE 5
int graph[NODE][NODE] = {
   {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[NODE];
// Function to display the Hamiltonian cycle
void displayCycle() {
   printf("Cycle Found: ");
   for (int i = 0; i < NODE; i++)
      printf("%d ", path[i]);
   // Print the first vertex again
   printf("%d
", path[0]);
}
// Function to check if adding vertex v to the path is valid
int isValid(int v, int k) {
   // If there is no edge between path[k-1] and v
   if (graph[path[k - 1]][v] == 0)
      return 0;
   // Check if vertex v is already taken in the path
   for (int i = 0; i < k; i++)
      if (path[i] == v)
         return 0;
   return 1;
}
// Function to find the Hamiltonian cycle
int cycleFound(int k) {
   // When all vertices are in the path
   if (k == NODE) {
      // Check if there is an edge between the last and first vertex
      if (graph[path[k - 1]][path[0]] == 1)
         return 1;
      else
         return 0;
   }
   // Try adding each vertex (except the starting point) to the path
   for (int v = 1; v < NODE; v++) {
      if (isValid(v, k)) {
         path[k] = v;
         if (cycleFound(k + 1) == 1)
            return 1;
         // Backtrack: Remove v from the path
         path[k] = -1;
      }
   }
   return 0;
}
// Function to find and display the Hamiltonian cycle
int hamiltonianCycle() {
   for (int i = 0; i < NODE; i++)
      path[i] = -1;
   // Set the first vertex as 0
   path[0] = 0;
   if (cycleFound(1) == 0) {
      printf("Solution does not exist
");
      return 0;
   }
   displayCycle();
   return 1;
}
int main() {
   hamiltonianCycle();
   return 0;
}
#include <iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
   {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[NODE];
// Function to display the Hamiltonian cycle
void displayCycle() {
   cout << "Cycle Found: ";
   for (int i = 0; i < NODE; i++)
      cout << path[i] << " ";
   // Print the first vertex again      
   cout << path[0] << endl; 
}
// Function to check if adding vertex v to the path is valid
bool isValid(int v, int k) {
   // If there is no edge between path[k-1] and v
   if (graph[path[k - 1]][v] == 0)
      return false;
   // Check if vertex v is already taken in the path
   for (int i = 0; i < k; i++)
      if (path[i] == v)
         return false;
   return true;
}
// function to find the Hamiltonian cycle
bool cycleFound(int k) {
   // When all vertices are in the path
   if (k == NODE) {
      // Check if there is an edge between the last and first vertex
      if (graph[path[k - 1]][path[0]] == 1)
         return true;
      else
         return false;
   }
   // adding each vertex to the path
   for (int v = 1; v < NODE; v++) {
      if (isValid(v, k)) {
         path[k] = v;
         if (cycleFound(k + 1) == true)
            return true;
         // Remove v from the path
         path[k] = -1;
      }
   }
   return false;
}
// Function to find and display the Hamiltonian cycle
bool hamiltonianCycle() {
   for (int i = 0; i < NODE; i++)
      path[i] = -1;
   // Set the first vertex as 0      
   path[0] = 0; 
   if (cycleFound(1) == false) {
      cout << "Solution does not exist" << endl;
      return false;
   }
   displayCycle();
   return true;
}
int main() {
   hamiltonianCycle();
}
public class HamiltonianCycle {
   static final int NODE = 5;
   static 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}
   };
   static int[] path = new int[NODE];
   // method to display the Hamiltonian cycle
   static void displayCycle() {
      System.out.print("Cycle Found: ");
      for (int i = 0; i < NODE; i++)
         System.out.print(path[i] + " ");
      // Print the first vertex again
      System.out.println(path[0]);
   }
   // method to check if adding vertex v to the path is valid
   static boolean isValid(int v, int k) {
      // If there is no edge between path[k-1] and v
      if (graph[path[k - 1]][v] == 0)
         return false;
      // Check if vertex v is already taken in the path
      for (int i = 0; i < k; i++)
         if (path[i] == v)
            return false;
      return true;
   }
   // method to find the Hamiltonian cycle
   static boolean cycleFound(int k) {
      // When all vertices are in the path
      if (k == NODE) {
         // Check if there is an edge between the last and first vertex
         if (graph[path[k - 1]][path[0]] == 1)
            return true;
         else
            return false;
      }
      // adding each vertex (except the starting point) to the path
      for (int v = 1; v < NODE; v++) {
         if (isValid(v, k)) {
            path[k] = v;
            if (cycleFound(k + 1))
               return true;
               // Remove v from the path
               path[k] = -1;
         }
      }
      return false;
   }
   // method to find and display the Hamiltonian cycle
   static boolean hamiltonianCycle() {
      for (int i = 0; i < NODE; i++)
         path[i] = -1;
      // Set the first vertex as 0
      path[0] = 0;
      if (!cycleFound(1)) {
         System.out.println("Solution does not exist");
         return false;
      }
      displayCycle();
      return true;
   }
   public static void main(String[] args) {
      hamiltonianCycle();
   }
}
NODE = 5
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 = [None] * NODE

# Function to display the Hamiltonian cycle
def displayCycle():
    print("Cycle Found:", end=" ")
    for i in range(NODE):
        print(path[i], end=" ")
    # Print the first vertex again
    print(path[0])

# Function to check if adding vertex v to the path is valid
def isValid(v, k):
    # If there is no edge between path[k-1] and v
    if graph[path[k - 1]][v] == 0:
        return False
    # Check if vertex v is already taken in the path
    for i in range(k):
        if path[i] == v:
            return False
    return True

# Function to find the Hamiltonian cycle
def cycleFound(k):
    # When all vertices are in the path
    if k == NODE:
        # Check if there is an edge between the last and first vertex
        if graph[path[k - 1]][path[0]] == 1:
            return True
        else:
            return False
    # adding each vertex (except the starting point) to the path
    for v in range(1, NODE):
        if isValid(v, k):
            path[k] = v
            if cycleFound(k + 1):
                return True
            # Remove v from the path
            path[k] = None
    return False

# Function to find and display the Hamiltonian cycle
def hamiltonianCycle():
    for i in range(NODE):
        path[i] = None
    # Set the first vertex as 0
    path[0] = 0
    if not cycleFound(1):
        print("Solution does not exist")
        return False
    displayCycle()
    return True

if __name__ == "__main__":
    hamiltonianCycle()

Output

Cycle Found: 0 1 2 4 3 0