增量式连通分量

本节介绍了一系列函数和类，它们协同工作以计算无向图的连通分量。这里使用的算法基于不相交集（快速并查集）数据结构 [8,27]，这是一种适用于图正在增长（边被添加）且需要重复更新连通分量信息的情况的好方法。此方法不涵盖图中边被添加和移除的情况，因此被称为增量式[42]（而不是完全动态的）。不相交集类在 不相交集 一节中描述。

以下五个操作是您将用于计算和维护连通分量的主要函数。这里使用的对象是一个图g，一个不相交集结构ds，以及顶点u和v.

• initialize_incremental_components(g, ds)
  不相交集结构的基本初始化。图中的每个顶点g都在其自己的集合中。
• incremental_components(g, ds)
  连通分量是基于图中的边计算的g，信息嵌入在ds.
• ds.find_set(v)
  提取顶点v的组件信息，来自不相交集。
• ds.union_set(u, v)
  当边 (u,v) 添加到图时，更新不相交集结构。

复杂度

整个过程的时间复杂度为 O(V + E alpha(E,V))，其中 E 是图中边的总数（过程结束时），V 是顶点的数量。alpha 是阿克曼函数的反函数，阿克曼函数具有爆炸性的递归指数增长。因此，其反函数增长非常缓慢。对于所有实际用途，alpha(m,n) <= 4，这意味着时间复杂度仅略大于 O(V + E)。

示例

在使用不相交集数据结构添加边的同时，维护图的连通分量。此示例的完整源代码可以在 examples/incremental_components.cpp 中找到。

using namespace boost;

int main(int argc, char* argv[])
{
  typedef adjacency_list  Graph;
  typedef graph_traits::vertex_descriptor Vertex;
  typedef graph_traits::vertices_size_type VertexIndex;

  const int VERTEX_COUNT = 6;
  Graph graph(VERTEX_COUNT);

  std::vector rank(num_vertices(graph));
  std::vector parent(num_vertices(graph));

  typedef VertexIndex* Rank;
  typedef Vertex* Parent;

  disjoint_sets ds(&rank[0], &parent[0]);

  initialize_incremental_components(graph, ds);
  incremental_components(graph, ds);

  graph_traits::edge_descriptor edge;
  bool flag;

  boost::tie(edge, flag) = add_edge(0, 1, graph);
  ds.union_set(0,1);

  boost::tie(edge, flag) = add_edge(1, 4, graph);
  ds.union_set(1,4);

  boost::tie(edge, flag) = add_edge(4, 0, graph);
  ds.union_set(4,0);

  boost::tie(edge, flag) = add_edge(2, 5, graph);
  ds.union_set(2,5);

  std::cout << "An undirected graph:" << std::endl;
  print_graph(graph, get(boost::vertex_index, graph));
  std::cout << std::endl;

  BOOST_FOREACH(Vertex current_vertex, vertices(graph)) {
    std::cout << "representative[" << current_vertex << "] = " <<
      ds.find_set(current_vertex) << std::endl;
  }

  std::cout << std::endl;

  typedef component_index Components;

  // NOTE: Because we're using vecS for the graph type, we're
  // effectively using identity_property_map for a vertex index map.
  // If we were to use listS instead, the index map would need to be
  // explicity passed to the component_index constructor.
  Components components(parent.begin(), parent.end());

  // Iterate through the component indices
  BOOST_FOREACH(VertexIndex current_index, components) {
    std::cout << "component " << current_index << " contains: ";

    // Iterate through the child vertex indices for [current_index]
    BOOST_FOREACH(VertexIndex child_index,
                  components[current_index]) {
      std::cout << child_index << " ";
    }

    std::cout << std::endl;
  }

  return (0);
}

initialize_incremental_components

template <class VertexListGraph, class DisjointSets>
void initialize_incremental_components(VertexListGraph& G, DisjointSets& ds)

这通过使图中的每个顶点成为其自身组件（或集合）的成员，为增量式连通分量算法准备不相交集数据结构。

定义位置

boost/graph/incremental_components.hpp

incremental_components

template <class EdgeListGraph, class DisjointSets>
void incremental_components(EdgeListGraph& g, DisjointSets& ds)

此函数计算图的连通分量，并将结果嵌入到不相交集数据结构中。

定义位置

boost/graph/incremental_components.hpp

类型要求

• 图类型必须是 EdgeListGraph 的模型。

same_component

template <class Vertex, class DisjointSet>
bool same_component(Vertex u, Vertex v, DisjointSet& ds)

此函数确定u和vu 和 v 是否在同一个组件中。

定义位置

boost/graph/incremental_components.hpp

类型要求

• 顶点必须与DisjointSets数据结构的 rank 和 parent 属性映射兼容。

component_index

component_index<Index>

这个component_index类为图的组件提供了类似 STL 容器的视图。每个组件都是一个类似容器的对象，并且通过operator[]提供访问。一个component_index对象使用从incremental_components()函数计算的不相交集中的 parent 属性初始化。可选地，可以传入一个顶点 -> 索引属性映射（identity_property_map默认使用）。

定义位置

boost/graph/incremental_components.hpp

成员

成员	描述
value_type/size_type	组件索引的类型（与Index).
size_type size()	返回图中组件的数量。
iterator/const_iterator	用于遍历可用组件索引 [0 到size()).
iterator begin() const	返回组件索引开始位置 (0) 的迭代器。
iterator end() const	返回组件索引结束位置之后的迭代器（size()).
std::pair<component_iterator, component_iterator> operator[size_type index] const	返回索引为index的组件的迭代器对，其中index在 [0,size()).