哈密顿回路

上一页
下一页

什么是哈密顿回路？

哈密顿回路（或环路）是在图中的一条路径，它访问每个顶点恰好一次并返回到起始顶点，形成一个闭环。只有当图包含哈密顿回路时，该图才被称为哈密顿图，否则被称为非哈密顿图。

图是一种抽象数据类型 (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
打印页面
上一页
下一页
广告