首页 文章

提升图了解顶点创建行为

提问于
浏览 次
1

我试图找出使用add_edge函数时顶点创建的行为 . 这是一个例子：

#include <iostream> 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>

using namespace boost;
typedef adjacency_list<> Graph;
typedef graph_traits<Graph>::vertex_iterator v_iter;

Graph g;
add_edge(1,2,g);
add_edge(1,4,g);
add_edge(2,3,g);
add_edge(2,6,g);

    std::cout << "num edges: " << num_edges(g) << "; num vertices: " << num_vertices(g) << std::endl;
for (std::pair<v_iter,v_iter> vp = vertices(g);  vp.first != vp.second; vp.first++) {
    std::cout << *vp.first << " ";
}

收益：

bash-3.2$ ./main
num edges: 4; num vertices: 7
0 1 2 3 4 5 6

为什么要创建这些顶点？该图有1,2,3,4和6作为顶点，总共5个不是7.看起来该函数创建了从0到顶点最高值的顶点 .

我真的不知道这里发生了什么，所以非常感谢任何帮助 .

非常感谢你提前 .

c++ boost graph

3 回答

  • 0

    邻接列表存储每个顶点的相邻节点：

    enter image description here

    根据文档：

    VertexList容器的选择器，用于表示图形的顶点列表 . 默认值：vecS

    这意味着 index into the vector 是顶点ID . 您不能拥有包含索引1但没有索引0的向量 . 因此，您将获得所有中间索引"for free" .

    当然，您可以调整一下：使用例如a listS 为顶点列表：看到它 Live On Coliru

    #include <iostream> 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <algorithm>

using namespace boost;
typedef adjacency_list<boost::listS> Graph;
typedef graph_traits<Graph>::vertex_iterator v_iter;

int main()
{
    Graph g;

    graph_traits<Graph>::vertex_descriptor v[] = {
        {}, // unused
        add_vertex(g), add_vertex(g), add_vertex(g),
        add_vertex(g), add_vertex(g), add_vertex(g),
    };

    add_edge(v[1], v[2], g);
    add_edge(v[1], v[4], g);
    add_edge(v[2], v[3], g);
    add_edge(v[2], v[6], g);

    std::cout << "num edges: " << num_edges(g) << "; num vertices: " << num_vertices(g) << std::endl;
    for (std::pair<v_iter, v_iter> vp = vertices(g); vp.first != vp.second; ++vp.first) {
        std::cout << std::distance(v, std::find(std::begin(v), std::end(v), *vp.first)) << " ";
    }
}

    打印

    num edges: 4; num vertices: 6
1 2 3 4 5 6 Press any key to continue . . .
    回复于
  • 0

    它会创建尽可能多的顶点和最高的数字，这意味着，当你写

    的add_edge（60）

    你将有61个从0开始的顶点

    回复于
  • 3

    只是想通了：这些值被视为索引 . 例如：

    add_edge(1,200);

    假设实际上有200个顶点并将第二个与201顶点连接起来 . 显然，它们之间的所有顶点都是自动创建的 .

    BW

    回复于

相关问题