数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究统计给定有向图中所有哈密顿路径
介绍
在图论中，哈密顿路径是指访问每个顶点恰好一次且不重复边的顶点序列。它以爱尔兰数学家威廉·罗恩·汉密尔顿爵士命名，他为包括图论在内的多个领域做出了重大贡献。在本文中，我们将深入了解如何使用 C++ 编程理解和统计有向图中所有可能的哈密顿路径。现在，轮到我们应用这些原理，揭开不同类型有向图中隐藏的秘密。
统计给定有向图中所有哈密顿路径
有向图由一组顶点和一组具有特定方向或方向的边连接而成。与边是双向或可以双向的无向图不同，有向图对其边施加严格的方向性。
输入
在以上代码中，我们以邻接矩阵作为输入，
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
当算法到达一个之前未访问过的顶点时，它将该顶点标记为已访问，并递归探索从该顶点出发所有可能的路径。如果算法恰好访问了所有顶点一次，则它将 hamilton_paths_count 变量加 1。
示例
算法从顶点 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：使用递归函数的 C++ 代码来统计给定有向图中所有哈密顿路径
统计给定有向图中所有可能的哈密顿路径需要一种称为回溯的广泛搜索策略。该方法系统地探索每个可行的解决方案，并在此过程中丢弃发现不可行的任何可能性。
算法
步骤 1 - 首先定义处理所需的的数据结构。
步骤 2 - 创建一个邻接矩阵（二维数组）来表示我们的有向图。
步骤 3 - 定义变量，例如 number_of_vertices 来存储总数，以及初始化为 0 的 hamilton_paths_count。
步骤 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;
}
输出
Total Hamiltonian Paths: 6
结论
最常用的编程语言是 C 和 C++，使用其中任何一种语言，我们都可以轻松处理哈密顿路径。此路径属于数学运算，通过使用图论，我们可以根据邻接矩阵的输入找到总路径。以上代码中使用的方法是递归函数。
312 次查看
