基于MST*2的TSP近似算法中先序遍历步骤的相关疑问

方法中先序遍历的具体操作逻辑 #

• 该流程中提到的preorder walk完全对应标准树结构的先序遍历规则，不存在特殊的自定义操作，核心逻辑和你认知中的树先序遍历一致：
  • 遍历起点固定为预先设定的根节点（即指定的路径起点/终点顶点1）
  • 顺序规则为：先访问当前节点，再递归遍历该节点的所有子节点，不需要记录回溯过程的重复访问节点
  • 举个可复现的操作示例：若MST结构为顶点1连接顶点2、顶点3，顶点2连接顶点4、顶点5，对应的先序访问序列为1→2→4→5→3，最后在序列末尾补充顶点1，就形成最终的近似TSP路径1→2→4→5→3→1
• 流程中的“walk”本质是对遍历记录规则的说明：如果沿着树边行走，遇到叶子节点需要回溯到父节点访问其他分支时，回溯经过的节点不会被重复计入最终的路径序列——这也是该算法能保证近似路径长度不超过最优TSP结果2倍的核心设计，不需要把回溯产生的重复路程算入最终路径权重。

使用Kruskal算法构造MST的适配方案 #

• 首先纠正一个基础认知偏差：无论使用Prim还是Kruskal算法构造的MST，本质都是无向连通树结构，不存在“生成有向图”的情况。你无法直接套用先序遍历的核心原因是：Kruskal算法本身不会输出带层级的树结构，只会返回一组构成最小生成树的无向边集合，没有显式记录节点间的父子关系，不是生成的结构不符合树的定义。
• 具体适配操作仅需两步即可完成：
  1. 拿到Kruskal输出的所有MST无向边后，从指定根节点（顶点1）出发做一次无向图深度优先搜索，为所有节点标记从根出发的层级关系：将与当前节点直接相连、且未被标记过的相邻节点，定义为当前节点的子节点
  2. 完成层级标记后，整个MST就成为以顶点1为根的有明确父子结构的有根树，可以直接套用标准先序遍历规则提取顶点序列
• 无需担心两种算法的MST结构差异对算法效果的影响：同一带权无向图的最小生成树总权重固定，哪怕不同算法生成的边组合存在区别，经先序遍历得到的近似TSP路径，依然满足“总长度不超过最优TSP路径2倍”的性能保证。

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