无向boost::adjacency_graph顶点出边无重复两两组合获取方法

核心思路 #

你当前的实现生成的是出边的排列结果，自然会出现顺序相反的重复边对。要得到无重复的两两组合，只需控制边的选取规则：永远只选取迭代位置靠后的边作为第二个元素，避免反向配对即可。

修正后实现代码 #

#include <vector>
#include <boost/graph/adjacency_list.hpp>

// 假设你的edge类型、Graph类型已经按业务需求完成定义
std::vector<std::pair<edge, edge>> get_unique_edge_pairs(const Graph& graph) {
    std::vector<std::pair<edge, edge>> edges;
    for (const auto vertex : boost::make_iterator_range(boost::vertices(graph))) {
        // 先把当前顶点的所有出边存入临时vector，方便按索引访问
        std::vector<edge> vertex_edges(boost::out_edges(vertex, graph).first, 
                                       boost::out_edges(vertex, graph).second);
        // 出边数量小于2时无法生成边对，直接跳过减少无效计算
        if (vertex_edges.size() < 2) {
            continue;
        }
        // 外层循环从第0个边遍历到倒数第二个边
        for (size_t i = 0; i < vertex_edges.size() - 1; ++i) {
            // 内层循环从i的下一个边遍历到最后一个边，保证i < j，天然不会生成反向重复对
            for (size_t j = i + 1; j < vertex_edges.size(); ++j) {
                edges.emplace_back(vertex_edges[i], vertex_edges[j]);
            }
        }
    }
    return edges;
}

逻辑说明 #

• 先将单个顶点的所有出边转存到临时vector，规避boost边迭代器无法随机访问的问题，降低循环控制复杂度
• 通过i < j的索引限制，每个无序边对只会被生成一次，完全匹配示例要求：
  • 示例1中顶点1有2条出边，生成1组组合，其余顶点出边数<2返回空
  • 示例2中顶点1有3条出边，生成C(3,2)=3组组合，和需求结果完全一致
• 相比额外对边目标顶点排序、去重的实现，该方案时间复杂度为O(n)（n为所有顶点的出边组合总数），没有额外的比较和去重开销，性能最优

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