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 推回到保存顶点 v 的邻接列表的 vector 中。 vector 数组的每个索引(名为顶点)表示图中每个顶点 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() 访问它。 .