c++ - 尝试使用 vector 数组实现图形

Question

我正在尝试使用 vector 数组实现图形。我很难做到这一点。 vector 将保存与顶点 v 相邻的顶点，顶点 v 是名为 uvertices 的数组的索引。

这就是我目前所拥有的。

class Graph {


public:

    int V;          //this will represent the number of vertices in the graph

std::vector<int>* vertices;

 Graph(int V) {

    vertices = new std::vector<int>[V];

  }

在这里，我创建了(或认为并打算创建)一个大小为 V 的数组(V 是图中顶点的数量)，其中包含 vector 。然后我希望能够创建边缘，所以我有

void Graph::insert_edge(int v, int u) {


}

作为一种方法。我想将值 u push_back 到包含顶点 v 的邻接列表的 vector 中。我的 vector 数组(名为 vertices)的每个索引代表图中每个顶点 v 的标识符。所以我想做类似的事情

  vertices[v].push_back(u);

我惊讶地发现，当我输入 vertices[v]. 时，Intellisense 给了我一个可能的函数列表，包括 push_back。我感到惊讶的原因是因为我实际上并没有创建任何 vector ，但我就这样离开了。这显然是行不通的，所以我开始调试，我意识到每当我第一次调用 insert_edge 时，它​​都会告诉我数组“顶点”的大小和容量为 0。尽管我将图形数据结构创建为

Graph G(8);

我花了大约两个小时来弄清楚如何使用它，但我没有成功。

我如何做到这一点，以便在插入边时，我可以查看顶点数组中的正确索引 v，并访问该数组索引所包含的 vector 的 push_back 函数，以便我可以添加顶点u到顶点v的邻接表。

此外，我真的真的真的真的恳求如果人们给我投反对票或投票结束我的主题，请告诉我原因。花时间把所有这些都写下来并确保它被清楚地写出来只是为了被否决而没有人告诉我他们为什么要否决我，这真是令人沮丧。

Answer 1

I was surprised to find that when I typed vertices[v]., Intellisense gave me a list of possible functions, including push_back. The reason I was surprised was because I hadn't actually created any of the vectors.

这不足为奇。动态数组是在运行时 分配的，而智能感知和所有其他静态分析器都不运行代码，因此它们永远无法判断变量在运行时的状态。 Intellisense 确实知道 vertices[v] 的类型是 std::vector<int>它知道该类型有哪些成员函数。

但是您也不必感到惊讶，因为您确实创建了 vector 。在 Graph 的构造函数中.

I realized that whenever I first call insert_edge, it tells me the size and the capacity of my array "vertices" is 0.

这里有个误区。 vertices是一个指针。并且在构造函数运行后，它指向一 block 内存，该内存块是恰好为V的动态数组。 std::vector<int> 的实例. vertices没有 size 这样的成员或 capacity .施工后，每std::vector<int>然而，在该动态数组中是 空的。直到你插入顶点。

This is obviously not working.

你的 insert_edge似乎工作正常。但是你确实有内存泄漏的问题(除非你有一个你没有显示的正确的析构函数)和不正确的复制构造函数和复制赋值运算符的问题(不遵循三的规则......除非你已经完成了那但没有显示)。您可以通过使用 vector 的 vector 而不是手动管理内存来解决这两个问题。

How do I Make it so that when an edge is inserted, I can look at the correct index v in the vertices array, and access the push_back function of the vector that that index of the array holds so that I can add the vertex u to the adjacency list of vertex v.

你已经想通了:

vertices[v].push_back(u);

相同的语法对于 vector 的 vector 也是正确的。

您也从未设置 Graph::V , 但如果你使用 vector 的 vector ，你就不再需要它了，因为它可以通过 vertices.size() 访问。 .