如何在存在孤立顶点时使用boost::connected_components？

问题背景 #

Boost官方的connected_components示例代码可正确计算图的连通分量，但未覆盖孤立顶点场景——当通过add_vertex(6, G)添加无任何边连接的孤立顶点时，该顶点无法被识别为单独的连通分量。

修改方案 #

原示例的核心问题是：connected_components算法仅遍历有边关联的顶点，孤立顶点的分量ID会保持默认值（通常为0），无法被正确统计。只需两步即可修复：

1. 预先初始化所有顶点的分量ID #

在调用算法前，为每个顶点的分量ID设置一个特殊初始值（比如-1），标记为未被处理状态：

// 初始化分量容器，所有顶点ID设为-1
std::vector<int> component(num_vertices(G), -1);

2. 补全孤立顶点的分量信息 #

调用connected_components后，遍历所有顶点，对未被算法处理的顶点（分量ID仍为-1）分配唯一的分量编号：

int num_components = connected_components(G, &component[0]);

// 遍历所有顶点，处理孤立节点
for (auto v : boost::make_iterator_range(vertices(G))) {
    if (component[v] == -1) {
        component[v] = num_components++;
    }
}

补充说明 #

• connected_components基于图的边做遍历，孤立顶点不在算法的访问路径中，因此必须手动处理。
• 用-1作为初始值是为了和算法生成的从0开始的分量ID做区分，避免统计混淆。

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