增量连通分量

本节描述了一系列函数和类，它们协同工作以计算无向图的连通分量。此处使用的算法基于不相交集（快速并查集）数据结构 [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 α(E,V))，其中E是图中（在过程结束时）的边的总数，V是顶点的数量。α是阿克曼函数的反函数，它具有爆炸性的递归指数增长。因此，它的反函数增长非常缓慢。实际上，α(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和v是否在同一个分量中。

定义位置

boost/graph/incremental_components.hpp

类型要求

• 顶点必须与不相交集的秩和父节点属性映射兼容DisjointSets数据结构。

component_index

component_index<Index>

该component_index类为图的分量提供了一个类似STL容器的视图。每个分量都是一个类似容器的对象，可以通过operator[]进行访问。一个component_index对象使用从incremental_components()函数计算的不相交集中的父节点属性进行初始化。可选地，传入一个顶点到索引的属性映射（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 operator[](size_type index) const	返回索引为index的分量的迭代器对，其中index在[0，size()).