基于改进Prim算法的图路径优化：如何进一步减少单边路径数量

我正在开发代码，目标是在复杂图中找到满足以下要求的最优路径集合：

• 覆盖每条边恰好一次
• 从符合条件的集合中选出路径最长、单边路径（仅含2个顶点的路径）数量最少的集合

已实现的修改版Prim算法 #

根据@ravenspoint的建议，我实现了调整后的Prim算法，具体步骤如下：

1. 从某一顶点出发，选择权重（顶点间笛卡尔距离）最小的邻接顶点，将对应[起始顶点,新顶点]边加入已访问列表；
2. 当路径中至少包含2个顶点时，同时从路径的首尾顶点继续搜索；
3. 路径完成后检查已遍历完成的顶点。

执行方式与原最优选择逻辑 #

我让代码遍历所有顶点作为起始点执行，最终得到n条路径（n为顶点总数）。
原本计划通过以下逻辑选择最优迭代结果：

for each iteration
    - select the 1-Edge paths 
    - measure their weight (aka length)
    - pick the minimum
end

在所有迭代的最小单边路径权重中，选取对应最小权重最大的迭代结果。我的思路是，基于最小边权重选择的话，单边路径更可能具有较高权重（即长度）。

当前问题 #

但目前单边路径数量仍与之前相近，约占总边数的30%，我希望能进一步减少该类路径的数量。

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