C++ 在给定的有向图中计算所有哈密顿路径

介绍

在图论中，哈密顿路径是一个顶点序列，每个顶点都恰好访问一次，没有重复边。它以爱尔兰数学家威廉·罗恩·哈密顿爵士命名，他在图论等多个领域做出了重要贡献。在本文中，我们将深入研究使用C++编程来理解和计算有向图中所有可能的哈密顿路径。现在，我们就可以应用这些原理，并揭示不同类型的有向图中隐藏的秘密。

在给定的有向图中计算所有哈密顿路径

有向图由一组由具有特定方向或方向的边连接的顶点组成。与无向图不同，其中边是双向的或可以朝两个方向走的，有向图对其边施加了严格的方向性。

输入

在上述代码中，我们将输入作为邻接矩阵。

当算法到达一个之前没有访问过的顶点时，它会将该顶点标记为已访问，并递归地探索从该顶点出发的所有可能的路径。如果算法正好访问了所有顶点一次，它将通过增加hamilton_paths_count变量的值来计算哈密顿路径的数量。

示例

算法从顶点0开始，并递归地探索从该顶点出发的所有可能的路径。算法使用visited_nodes数组来记录迄今为止已经访问过的顶点。

可以构建的六条哈密顿路径如下：

0 -> 1 -> 2 -> 3 -> 4
0 -> 3 -> 2 -> 1 -> 4
0 -> 3 -> 4 -> 1 -> 2
0 -> 1 -> 4 -> 3 -> 2
0 -> 2 -> 1 -> 4 -> 3
0 -> 2 -> 3 -> 4 -> 1

所以，给定的有向图中计数为6。

方法1：使用递归函数在给定的有向图中计数所有Hamiltonian路径的C++代码

在给定的有向图中计数所有可能的Hamiltonian路径需要广泛搜索策略，称为回溯。该方法系统地探索每个可行的解决方案，并且在途中丢弃任何被发现的不可行可能性。

算法

步骤1 - 开始定义必要的数据结构。
步骤2 - 创建一个邻接矩阵（2D数组）来表示我们的有向图。
步骤3 - 定义变量，如number_of_vertices来存储总计数，hamilton_paths_count初始化为0。
步骤4 - 使用另一个数组visited_nodes来跟踪访问过的节点，最初将所有顶点标记为未访问。
步骤5 - 给定顶点，我们必须寻找它们之间的边，并避开任何已经被函数访问过的顶点。
步骤6 - 开发所需的计算函数。
- createGraph() - 根据用户定义的输入或随机生成方法初始化表示顶点连接的邻接矩阵。
- hamiltonPath() - 递归函数，探索每种可能性，同时确保不重复访问已经遍历过的顶点。
步骤7 - 打印输出结果。

示例

//The header file to include the input and output is used
// Maximum number of vertices
#include<iostream>
#define V 5 

// Declaring variable for counting Hamiltonian paths
//Adjacent matrix is initialized 
int hamilton_paths_count = 0; 
int graph[V][V] = {
   {0, 1, 0, 1, 0},
   {1, 0, 1, 1, 0},
   {0, 1, 0, 1, 1},
   {1, 1, 1, 0, 1},
   {0, 0, 1, 1, 0}
}; 
// Adjacency matrix representing the directed graph
bool visited_nodes[V];
//Implementation to obtain user-defined or random initialization of adjacency matrix
void createGraph() {

}

void hamiltonPath(int current_vertex, int total_vertices_visited) {
   // Base case: all vertices have been visited once
   // Increment count for a valid Hamiltonian path found
   if(total_vertices_visited == V) { 
      hamilton_paths_count++; 
      return;
   }
   // Here, before invoking this function recursively, we make sure that an edge exists between two connected vertices and that the following vertices have not already been visited*/    
   visited_nodes[current_vertex] = true; 
   for(int i=0;i<V;i++) {
      if(graph[current_vertex][i]!=0 && !visited_nodes[i]) {   
         hamiltonPath(i, total_vertices_visited+1);     
         //We increment the total_vertices_visited by 1 and move on to check if there are more valid paths from this point. Rinse and repeat!
         //Once a recursive iteration is complete, reset 'visited' status while backtracking **/
         visited_nodes[i] = false;              
      }
   }    
}
//main function to test the code
int main() {
   createGraph(); 

   memset(visited_nodes,false,sizeof(visited_nodes)); // Initialize all nodes as unvisited
   hamiltonPath(0,1);

   std::cout << "Total Hamiltonian Paths: " <<hamilton_paths_count<<std::endl;

   return 0;
}