strong_components

// named parameter version
template <class Graph, class ComponentMap, class P, class T, class R>
typename property_traits<ComponentMap>::value_type
strong_components(Graph& g, ComponentMap comp,
    const bgl_named_params<P, T, R>& params = all defaults)

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

Thestrong_components()函数使用基于 DFS 的 Tarjan 算法计算有向图的强连通分量 [41]。

算法的输出记录在组件属性映射中comp，它将包含数字，给出分配给每个顶点的组件 ID。 组件的数量是函数的返回值。

定义于

boost/graph/strong_components.hpp

定义

有向图 G=(V,E) 的强连通分量 是一个顶点的最大集合 U，它在 V 中，使得对于每对顶点 u 和 v 在 U 中，我们既有从 u 到 v 的路径，也有从 v 到 u 的路径。 也就是说 u 和 v 可以互相到达。

参数

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

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

命名参数

算法使用它来记录每个顶点的候选根顶点。算法结束时，每个组件都有一个根顶点，并且get(r_map, v)返回组件顶点v所属的根顶点。 TheRootMap必须是一个 读/写属性映射，其中键类型和值类型是图的顶点描述符类型。
默认值： 一个 iterator_property_map 从一个std::vector顶点描述符的 的大小num_vertices(g)创建，并使用i_map作为索引映射。
Python：不支持的参数。

算法使用它来跟踪顶点的 DFS 顺序。 TheTimeMap必须是 读/写属性映射 的模型，并且其值类型必须是整数类型。 键类型必须是图的顶点描述符类型。
默认值： 一个 iterator_property_map 从一个std::vector整数的 的大小num_vertices(g)创建，并使用i_map作为索引映射。
Python：不支持的参数。

算法使用它来跟踪其在图中的进度。 The 类型ColorMap必须是 读/写属性映射 的模型，并且其键类型必须是图的顶点描述符类型，颜色映射的值类型必须是 ColorValue 的模型。
默认值： 一个 iterator_property_map 从一个std::vectorofdefault_color_type的大小num_vertices(g)创建，并使用i_map作为索引映射。
Python：不支持的参数。

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

复杂度

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

另请参阅

示例

请参阅 examples/strong_components.cpp。