connected_components

// named parameter version
template <class VertexListGraph, class ComponentMap, class P, class T, class R>
typename property_traits<ComponentMap>::value_type
connected_components(VertexListGraph& G, ComponentMap comp,
    const bgl_named_params<P, T, R>& params = all defaults);

// there is not a non-named parameter version of this function

该connected_components()函数使用基于 DFS 的方法计算无向图的连通分量。无向图的**连通分量**是一组相互可达的顶点。如果需要在图增长时维护连通分量，则函数 incremental_components() 的基于不相交集的方法更快。对于“静态”图，这种基于 DFS 的方法更快 [8]。

算法的输出记录在分量属性映射中comp，其中包含为每个顶点分配的分量编号。分量的总数是函数的返回值。

定义位置

boost/graph/connected_components.hpp

参数

一个无向图。图类型必须是 顶点列表图 和 关联图 的模型。
Python：参数名为graph.

该算法计算图中连通分量的数量，并为每个分量分配一个整数标签。然后，该算法通过在分量属性映射中记录分量编号来记录图中每个顶点所属的分量。该ComponentMap类型必须是 可写属性映射 的模型。值类型应为整数类型，最好与图的vertices_size_type相同。键类型必须是图的顶点描述符类型。
Python：必须是vertex_int_map用于该图。
Python 默认值: graph.get_vertex_int_map("component")

命名参数

算法使用此参数来跟踪其在图中的进度。类型ColorMap必须是 读/写属性映射 的模型，其键类型必须是图的顶点描述符类型，颜色映射的值类型必须是 ColorValue 的模型。
默认值：一个从std::vector创建的 iterator_property_map，其中包含大小为default_color_type的num_vertices(g)个元素，并使用i_map作为索引映射。
Python：颜色映射必须是vertex_color_map用于该图。

这将每个顶点映射到范围[0, num_vertices(g))内的整数。仅当使用默认颜色属性映射时，才需要此参数。类型VertexIndexMap必须是 可读属性映射 的模型。映射的值类型必须是整数类型。图的顶点描述符类型需要可用作映射的键类型。
默认值 get(vertex_index, g)。注意：如果使用此默认值，请确保您的图具有内部vertex_index属性。例如，adjacency_list使用VertexList=listS没有内部vertex_index属性。
Python：不支持此参数。

复杂度

连通分量算法的时间复杂度也是 *O(V + E)*。

另请参阅

示例

文件 examples/connected_components.cpp 包含计算无向图的连通分量的示例。