如何基于Kruskal算法实现仅首尾插节点的TSP及End(u)/End(v)功能

你用到的是仅允许在路径头尾拼接的Kruskal变种TSP算法，本质是生成一条总权值最小的哈密顿路径，所有节点度数最大为2，无分支和环。
其中End(u)函数的核心作用是：判断节点u是否为其所在路径段的端点，仅端点允许参与拼接，否则会出现度数>2的分支节点。

实现思路 #

普通并查集仅能判断节点是否连通，无法识别端点，因此需要新增度数数组记录每个节点的连接度数：

• 初始状态下每个节点独立为一个路径段，度数为0，自身就是端点
• 路径中间节点的度数为2，不可再参与拼接
• 路径头尾端点的度数为1（单节点路径度数为0），可参与拼接

End(u)的判断逻辑等价于deg[u] < 2，只要满足该条件，u就是所在路径段的可用端点。

现有代码改造方案 #

1. 新增类成员变量 #

在Graph类的私有成员中新增度数数组，记录每个节点的连接度数：

private:
  vector<pair<int, edge> > G;  // 原始图边集
  vector<pair<int, edge> > T;  // 生成的TSP路径边集
  int *parent;
  int *deg; // 节点度数数组
  int V;  // 总节点数

2. 初始化度数数组 #

修改构造函数，初始化新增的度数数组：

Graph::Graph(int V) {
  parent = new int[V];
  deg = new int[V];
  for (int i = 0; i < V; i++) {
    parent[i] = i;
    deg[i] = 0; // 初始单节点路径度数为0，自身为端点
  }
  G.clear();
  T.clear();
}

3. 修改Kruskal主逻辑 #

在原有连通性判断前，新增端点校验，符合要求才将边加入路径：

void Graph::kruskal() {
  int i, u, v, uRep, vRep;
  sort(G.begin(), G.end()); // 按边权升序排序
  // 哈密顿路径共V个节点，只需V-1条边，凑够即可提前退出
  for (i = 0; i < G.size() && T.size() < V - 1; i++) {
    u = G[i].second.first;
    v = G[i].second.second;
    // 非端点节点跳过，避免生成度数大于2的节点
    if (deg[u] >= 2 || deg[v] >= 2) continue;
    uRep = find_set(u);
    vRep = find_set(v);
    // 不在同一连通分量，避免成环
    if (uRep != vRep) {
      T.push_back(G[i]);
      union_set(uRep, vRep);
      // 拼接后两个端点度数各加1
      deg[u]++;
      deg[v]++;
    }
  }
}

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