如何在无向图中查找所有每个节点仅遍历一次的可行路径

你要找的是无向图的所有哈密顿路径，核心采用带剪枝的回溯DFS实现，无需手动录入边关系，直接传入邻接矩阵即可运行，支持任意起点、任意终点，每条路径独立输出。

核心逻辑 #

1. 输入直接读取25×25邻接矩阵，判断两节点是否连通直接取adj[u][v]的值，非0即为连通
2. 外层遍历所有节点作为路径起点，每个起点单独初始化访问标记和路径缓存
3. 递归回溯扩展路径：每走到一个节点就标记为已访问，加入当前路径；当路径长度等于25时，直接保存该路径；递归返回后自动回溯状态，尝试其他分支
4. 加入剪枝规则提前排除不可能的分支，大幅降低运算量

代码实现（Python版） #

import pandas as pd

def find_all_hamiltonian_paths(adj):
    node_count = len(adj)
    result = []

    def backtrack(current_node, visited, current_path):
        # 路径长度等于节点数，符合要求，存入结果
        if len(current_path) == node_count:
            result.append(current_path.copy())
            return
        # 剪枝：当前节点剩余未访问邻居不足，直接终止该分支
        remaining_need = node_count - len(current_path)
        available_neighbor = 0
        for v in range(node_count):
            if not visited[v] and adj[current_node][v]:
                available_neighbor += 1
        if available_neighbor < remaining_need - 1:
            return
        # 遍历所有合法下一跳节点
        for next_node in range(node_count):
            if not visited[next_node] and adj[current_node][next_node]:
                visited[next_node] = True
                current_path.append(next_node)
                backtrack(next_node, visited, current_path)
                # 回溯状态
                current_path.pop()
                visited[next_node] = False

    # 遍历所有节点作为起点
    for start in range(node_count):
        visited = [False] * node_count
        visited[start] = True
        backtrack(start, visited, [start])
    
    return result

if __name__ == "__main__":
    # 从csv读取邻接矩阵，无需手动录入边，替换为你的文件路径即可
    adj = pd.read_csv("your_adj_matrix.csv", header=None).values.tolist()
    all_paths = find_all_hamiltonian_paths(adj)
    # 单独输出每条路径
    for path_id, path in enumerate(all_paths, 1):
        print(f"路径{path_id}: {path}")

优化说明 #

• 25个节点的哈密顿路径遍历属于NP完全问题，若你的图为稠密图，全量遍历耗时会非常长，可根据需求增加业务相关剪枝规则
• 运算量较大时可替换为C++实现，用32位整数作为位掩码存储访问状态，开启O2优化后速度可提升数十倍
• 无向图场景下若不需要区分路径方向，可固定起点为0，遍历完成后将所有路径反转即可得到全部反向路径，可减少一半运算量

其他语言适配 #

Java、JS、C++的核心逻辑和上述实现完全一致，仅语法存在差异：

• Java可以用boolean[]存储访问标记，用List<List<Integer>>存储结果
• JS可以用Set或者布尔数组存访问标记
• C++可以用vector<vector<int>>存邻接矩阵和结果，用uint32_t存访问掩码提升效率

内容的提问来源于stack exchange，提问作者Benjamin Tordjman