当存在没有边的顶点时如何使用boost::connected_components？

Question

boost 中的示例来自文档

https://www.boost.org/doc/libs/1_85_0/libs/graph/example/connected_components.cpp

//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

/*

  This example demonstrates the usage of the connected_components
  algorithm on a undirected graph. The example graphs come from
  "Introduction to Algorithms", Cormen, Leiserson, and Rivest p. 87
  (though we number the vertices from zero instead of one).

  Sample output:

  Total number of components: 3
  Vertex 0 is in component 0
  Vertex 1 is in component 0
  Vertex 2 is in component 1
  Vertex 3 is in component 2
  Vertex 4 is in component 0
  Vertex 5 is in component 1

 */

using namespace std;

int main(int , char* []) 
{
  using namespace boost;
  {
    typedef adjacency_list <vecS, vecS, undirectedS> Graph;

    Graph G;
    add_edge(0, 1, G);
    add_edge(1, 4, G);
    add_edge(4, 0, G);
    add_edge(2, 5, G);
    
    std::vector<int> component(num_vertices(G));
    int num = connected_components(G, &component[0]);
    
    std::vector<int>::size_type i;
    cout << "Total number of components: " << num << endl;
    for (i = 0; i != component.size(); ++i)
      cout << "Vertex " << i <<" is in component " << component[i] << endl;
    cout << endl;
  }
  return 0;
}

这个效果很好。

https://godbolt.org/z/3jYaEM9Ks

但是有一个问题。对于没有通过边连接到任何其他顶点的顶点呢？它本身应该以一个组件结尾。但是我不确定如何更改代码来实现此目的？

我尝试过添加

 add_vertex(6, G);

但是这种直觉不起作用。

Answer 1

但是有一个问题。对于没有通过边连接到任何其他顶点的顶点呢？它应该单独以一个组件结尾。

在您的示例中，顶点 #3 就是这样一个顶点。它已经在自己的组件中了。成功！

我尝试添加

add_vertex(6, G);

，但直觉不起作用。

我不知道那应该实现什么。您使用参数

add_vertex

调用

6

来初始化顶点属性。但你没有顶点属性 ́\(ツ)/́.

如果您想添加顶点，只需说

auto descriptor = add_vertex(G);

。但正如您在上面看到的，没有必要，因为顶点 3 已经未连接。

如果您想确保存在 7 个顶点 (0,1,2,3,4,5,6)，只需这样做：

Graph g(7);

现在它打印出来了，正如你所期望的：

Total number of components: 4
Vertex 0 is in component 0
Vertex 1 is in component 0
Vertex 2 is in component 1
Vertex 3 is in component 2
Vertex 4 is in component 0
Vertex 5 is in component 1
Vertex 6 is in component 3

奖金

如果您确实对

vecS

存储中的隐式顶点索引感到困惑，请比较：

住在Coliru

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>
#include <iostream>
#include <vector>

int main(int, char*[]) {
    using Graph = boost::adjacency_list<boost::vecS, boost::listS, boost::undirectedS>;
    using VDesc = Graph::vertex_descriptor;

    Graph g;
    std::array<VDesc, 7> vv;
    for (auto& v : vv)
        v = add_vertex(g);

    add_edge(vv[0], vv[1], g);
    add_edge(vv[1], vv[4], g);
    add_edge(vv[4], vv[0], g);
    add_edge(vv[2], vv[5], g);

    std::map<VDesc, int>    component;
    std::map<VDesc, size_t> index;

    auto compmap = boost::make_assoc_property_map(component);
    auto idmap   = boost::make_assoc_property_map(index);

    for (auto v : boost::make_iterator_range(vertices(g)))
        index.emplace(v, index.size());
    int num = connected_components( //
        g,                          //
        compmap,
        boost::vertex_index_map(idmap));

    std::cout << "Total number of components: " << num << std::endl;

    // Iterate vertices
    for (auto v : boost::make_iterator_range(vertices(g)))
        std::cout << "Vertex " << v << " (id " << idmap[v] << ") is in component " << compmap[v] << std::endl;

    // Iterate map
    std::cout << "Total number mappings: " << component.size() << std::endl;
    for (auto const& [v, comp] : component)
        std::cout << "Vertex " << v << " (id " << idmap[v] << ") is in component " << comp << std::endl;
    std::cout << std::endl;
}

打印例如

Total number of components: 4
Vertex 0x504000000050 (id 0) is in component 0
Vertex 0x504000000090 (id 1) is in component 0
Vertex 0x5040000000d0 (id 2) is in component 1
Vertex 0x504000000110 (id 3) is in component 2
Vertex 0x504000000150 (id 4) is in component 0
Vertex 0x504000000190 (id 5) is in component 1
Vertex 0x5040000001d0 (id 6) is in component 3
Total number mappings: 7
Vertex 0x504000000050 (id 0) is in component 0
Vertex 0x504000000090 (id 1) is in component 0
Vertex 0x5040000000d0 (id 2) is in component 1
Vertex 0x504000000110 (id 3) is in component 2
Vertex 0x504000000150 (id 4) is in component 0
Vertex 0x504000000190 (id 5) is in component 1
Vertex 0x5040000001d0 (id 6) is in component 3