中国邮路问题奇顶点全配对生成算法实现及现有C++代码错误修复

第一版代码问题原因 #

核心错误是返回值结构逻辑不符合需求：你将所有层级产生的单个配对都平铺开塞到同一个大vector中，没有区分「每一套完整的配对方案」。递归到最底层时返回空vector，导致上层拼接时只会把当前配对单独加入结果，不会将当前配对和下层返回的所有配对组合为完整方案。

修复后代码 #

std::vector<std::vector<int>> Postman::pairOdd(std::vector<int> vertices)
{   
    std::vector<std::vector<int>> all_schemes;
    if (vertices.empty()) {
        // 空顶点对应一个空方案，方便上层拼接配对
        all_schemes.push_back({});
        return all_schemes;
    }
    auto it = std::min_element(vertices.begin(), vertices.end());
    int i = *it;
    vertices.erase(it);
    for (int index = 0; index < vertices.size(); index++) {
        int j = vertices[index];
        vertices.erase(vertices.begin() + index);
        // 递归获取剩余顶点的所有配对方案
        auto sub_schemes = pairOdd(vertices);
        // 将当前配对{i,j}拼接到每个子方案头部，形成完整方案
        for (auto &sub : sub_schemes) {
            sub.insert(sub.begin(), {i, j});
            all_schemes.push_back(sub);
        }
        // 回溯恢复顶点列表，用于下一轮循环
        vertices.insert(vertices.begin() + index, j);
    }
    return all_schemes;
}

测试代码调整 #

修复后返回的每个子vector对应一套完整的配对方案，输出逻辑调整如下即可得到预期结果：

std::vector<std::vector<int>> res = pairOdd(std::vector<int>{1,2,3,4,5,6});
for (auto &scheme : res) {
    for (int k = 0; k < scheme.size(); k += 2) {
        std::cout << scheme[k] << " " << scheme[k+1] << "  ";
    }
    std::cout << std::endl;
}

第二版代码问题原因 #

出现重复配对的核心原因是缺少回溯操作：你在循环内部往list变量中push了in1和in2，但循环结束后没有将这两个元素弹出，导致下一轮循环迭代时list已经携带了上一轮的旧数据，最终产生重复的配对片段。

修复方案 #

只需要在递归调用结束后新增回溯逻辑，清理本次循环加入的元素即可：

if (in1 != 0 && in2 != 0) {
    list.push_back(in1);
    list.push_back(in2);
}
std::vector<std::vector<int>> returnValue = aaa(vertices, list, i, j);
pairs.insert(pairs.end(), returnValue.begin(), returnValue.end());
// 新增回溯逻辑
if (in1 != 0 && in2 != 0) {
    list.pop_back();
    list.pop_back();
}

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