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

参数

一个无向图。图类型必须是 Vertex List Graph 和 Incidence Graph 的模型。
Python：参数名为graph.

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

命名参数

算法使用此参数来跟踪其在图中的进度。类型ColorMap必须是 Read/Write Property Map 的模型，并且其键类型必须是图的顶点描述符类型，颜色映射的值类型必须是 ColorValue 的模型。
默认值： 从std::vector的default_color_type大小为num_vertices(g)并使用i_map作为索引映射的 iterator_property_map 创建。
Python：颜色映射必须是vertex_color_map图的 vertex_int_map。

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

复杂度

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

另请参阅

示例

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