用Rust实现哈密顿路径算法（从零开始掌握图论中的经典问题）

什么是哈密顿路径？

想象你有一张城市地图，每个城市是一个“节点”，城市之间的道路是“边”。哈密顿路径就是规划一条旅行路线，让你恰好访问每一个城市一次，且不重复。这听起来简单，但对大型图来说，计算复杂度极高——属于 NP-完全问题。

在本教程中，我们将使用 Rust编程教程 中常见的深度优先搜索（DFS）方法，暴力尝试所有可能路径，直到找到满足条件的哈密顿路径。

准备工作：Rust环境搭建

确保你已安装 Rust。打开终端，运行：

rustc --version

如果没有安装，请访问 https://www.rust-lang.org/ 下载并安装。

算法思路

我们将采用以下步骤实现 Rust哈密顿路径 算法：

1. 用邻接矩阵表示图（二维布尔数组）
2. 从任意起点开始，使用 DFS 递归尝试所有邻居
3. 记录当前路径，并标记已访问节点
4. 当路径长度等于节点总数时，说明找到了哈密顿路径

完整代码实现

下面是一个完整的、可运行的 Rust 程序：

fn hamiltonian_path(graph: &Vec<Vec<bool>>, path: &mut Vec<usize>, visited: &mut Vec<bool>, n: usize) -> bool {    // 如果路径包含所有节点，说明找到哈密顿路径    if path.len() == n {        return true;    }    let last = *path.last().unwrap();    // 尝试所有未访问且与当前节点相连的邻居    for next in 0..n {        if graph[last][next] && !visited[next] {            visited[next] = true;            path.push(next);            if hamiltonian_path(graph, path, visited, n) {                return true;            }            // 回溯            visited[next] = false;            path.pop();        }    }    false}fn find_hamiltonian_path(graph: &Vec<Vec<bool>>) -> Option<Vec<usize>> {    let n = graph.len();    if n == 0 {        return None;    }    // 尝试从每个节点作为起点    for start in 0..n {        let mut path = vec![start];        let mut visited = vec![false; n];        visited[start] = true;        if hamiltonian_path(graph, &mut path, &mut visited, n) {            return Some(path);        }    }    None}fn main() {    // 示例图：5个节点    let graph = vec![        vec![false, true,  true,  false, false],        vec![true,  false, true,  true,  false],        vec![true,  true,  false, true,  true ],        vec![false, true,  true,  false, true ],        vec![false, false, true,  true,  false]    ];    match find_hamiltonian_path(&graph) {        Some(path) => {            println!("找到哈密顿路径: {:?}", path);        },        None => {            println!("未找到哈密顿路径");        }    }}

代码详解

• hamiltonian_path 是递归函数，尝试从当前路径扩展
• visited 数组防止重复访问节点
• 使用 回溯 技术：如果某条路径走不通，就撤销选择，尝试其他可能
• find_hamiltonian_path 尝试所有可能的起点，提高成功率

运行与测试

将上述代码保存为 hamilton.rs，然后在终端运行：

rustc hamilton.rs./hamilton

你可能会看到输出：

找到哈密顿路径: [0, 1, 3, 4, 2]

性能与优化提示

当前实现是指数级时间复杂度 O(n!)，适用于小规模图（n ≤ 20）。对于大规模图，可考虑启发式算法或动态规划（如 Held-Karp 算法），但这超出了本 哈密顿路径实现 教程的范围。

总结

通过本教程，你已经学会了如何用 Rust 实现哈密顿路径算法。我们使用了深度优先搜索和回溯技术，这是解决组合问题的经典方法。虽然该算法效率不高，但它清晰展示了 图论算法 的核心思想。

希望这篇 Rust编程教程 能帮助你理解哈密顿路径，并激发你探索更多算法的兴趣！