强连通分量

// 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

函数strong_components()使用基于深度优先搜索的 Tarjan 算法计算有向图的强连通分量 [41]。

算法的输出记录在分量属性映射comp中，该映射将包含赋予每个顶点的分量 ID 号。分量的数量是函数的返回值。

定义位置

boost/graph/strong_components.hpp

定义

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

参数

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

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

命名参数

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

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

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

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

复杂度

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

另请参阅

示例

参见 examples/strong_components.cpp。