哈密頓迴路

上一頁
下一頁

什麼是哈密頓迴路？

哈密頓迴路（或環路）是在圖中的一條路徑，它訪問每個頂點恰好一次並返回到起始頂點，形成一個閉環。只有當圖包含哈密頓迴路時，該圖才被稱為哈密頓圖，否則被稱為非哈密頓圖。

圖是一種抽象資料型別 (ADT)，由透過連結連線的一組物件組成。

哈密頓迴路問題的實際應用可見於網路設計、交付系統等許多領域。但是，該問題的解決方案僅適用於小型圖，而不適用於大型圖。

輸入輸出場景

假設給定的無向圖 G(V, E) 及其鄰接矩陣如下所示：

Hamiltonian Cycle

可以使用回溯演算法在上述圖中查詢哈密頓路徑。如果找到，演算法將返回路徑；如果沒有找到，則返回 false。對於這種情況，輸出應為 (0, 1, 2, 4, 3, 0)。

使用回溯法查詢哈密頓迴路

解決哈密頓迴路問題的樸素方法是生成所有可能的頂點配置，並檢查是否有任何配置滿足給定的約束條件。但是，這種方法不適用於大型圖，因為其時間複雜度為 (O(N!))。

以下步驟解釋了回溯方法的工作原理：

  • 首先，建立一個空的路徑陣列，並將起始頂點 0 新增到其中。

  • 接下來，從頂點 1 開始，然後逐個新增其他頂點。

  • 新增頂點時，檢查給定頂點是否與先前新增的頂點相鄰，並且尚未新增。

  • 如果找到任何這樣的頂點，則將其作為解決方案的一部分新增到路徑中，否則返回 false。

示例

以下示例演示如何在給定的無向圖中查詢哈密頓迴路。

C C++ Java Python
#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\n", 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\n");
      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()

輸出

Cycle Found: 0 1 2 4 3 0
列印頁面
上一頁
下一頁
廣告