咨询：有向加权multigraph中遍历所有节点的有向闭迹求解算法

核心概念澄清 #

你要找的是边不重复、起点与终点相同、且覆盖图中所有节点至少一次的有向闭迹，和哈密顿回路的核心差异在于：

• 哈密顿回路要求除首尾节点外，其他节点仅能被访问一次；
• 你的需求允许节点重复访问，仅限制边不重复，且必须覆盖所有节点。

算法选择与思路 #

1. 可行性前提 #

首先你的图必须是强连通图——即任意两个节点之间都存在双向的有向路径，否则无法形成覆盖所有节点的闭迹（存在节点无法从起点到达，或无法从该节点返回起点）。

2. 核心算法：回溯枚举法 #

因为需要找到所有符合要求的闭迹，最直接的方案是基于回溯的枚举思路，适配有向多重图的特性：

• 从起点x出发，维护两个关键集合：已走过的边集合（由于是多重图，需区分同一对节点间的不同边）、已访问的节点集合；
• 每次选择当前节点的一条未使用出边，移动到下一个节点，更新上述两个集合；
• 当回到起点x，且已访问节点集合覆盖图中所有节点时，记录这条闭迹；
• 回溯尝试所有未探索的边选择，遍历所有可能的路径。

3. 哈密顿回路算法的适用性 #

常规哈密顿回路算法无法直接使用或修改后满足需求：

• 哈密顿算法的核心逻辑是限制节点仅访问一次（除首尾），和你允许节点重复访问的需求完全冲突；
• 即使修改算法取消节点访问限制，此时算法本质已变成回溯枚举闭迹的思路，不再是哈密顿回路算法的范畴；
• 另外，多数哈密顿算法针对简单图设计，适配多重图需要额外处理同节点对间的多条边，进一步增加复杂度，不如直接使用回溯法高效。

4. 优化建议 #

如果图的规模较大，纯回溯效率较低，可以加入剪枝策略：

• 若当前路径已无法到达任何未访问的节点，直接终止该分支；
• 利用多重图的边对称性，避免重复枚举结构相同的闭迹；
• 若仅需要找到任意一条符合要求的闭迹而非全部，可以优先探索通往未访问节点的边，减少无效遍历。

内容的提问来源于stack exchange，提问作者Alexander Jafari