C++ Boost Graph - 为什么我有一个额外的顶点？

Question

我有一个图，其顶点和边是自定义类型。在下面的示例中，我创建了具有 4 个顶点和 4 条边的图形。但是，当我遍历顶点以打印它时，系统总共输出 5 个顶点。我不确定我做错了什么，我希望有人能够启发我。

struct Vertex { int id; double data; };
struct Edge { float distance; };

int main(int, char** argv)
{

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Vertex, Edge> Graph;

//instantiate a graph
Graph g;

//add vertices
boost::add_vertex(Vertex{ 1, 1.1 }, g);
boost::add_vertex(Vertex{ 2, 2.2 }, g);
boost::add_vertex(Vertex{ 3, 3.3 }, g);
boost::add_vertex(Vertex{ 4, 4.4 }, g);

boost::add_edge(1, 2, g);
boost::add_edge(1, 4, g);
boost::add_edge(2, 4, g);   
boost::add_edge(1, 3, g);

// Iterate through the vertices and print them out
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = boost::vertices(g); vp.first != vp.second; vp.first++)
    std::cout << g[*(vp.first)].id << " " << g[*(vp.first)].data << std::endl;

// Iterate through the edges and print them out
auto es = boost::edges(g);
for (auto eit = es.first; eit != es.second; ++eit) {
    std::cout << boost::source(*eit, g) << ' ' << boost::target(*eit, g) << std::endl;
}

输出结果如下

1 1.1
2 2.2
3 3.3
4 4.4
0 0
1 2
1 4
1 3
2 4

Answer 1

来自docs :

If the VertexList of the graph is vecS, then the graph has a builtin vertex indices accessed via the property map for the vertex_index_t property. The indices fall in the range [0, num_vertices(g)) and are contiguous.

add_vertex 的描述没有明确说明，但我相信以上内容要求将带有描述符 u 的顶点添加到图中必须创建从 0 到 u 的顶点，如果它们中的任何一个不存在的话已经存在。从根本上说，它只是将顶点 vector 的大小调整为 u + 1，这样 u 就变成了一个有效的索引。