c++ - 填充一个包含指向列表的指针的 vector

Question

我初始化一个指针 vector ，每个指针指向一个邻居列表，以实现图形的邻接列表表示。

class Graph
{
public:
     Graph(int V) : vertices(V) {}
     // Member functions for Graph class
     void addEdge();
     void print();
     void type(string);
private:
     vector<list<int> *> vertices;
};

addEdge 函数要求用户输入从哪个顶点到另一个顶点的边。我认为填充 vector 的某个地方存在错误。

void Graph::addEdge()
{
    int v, w;
    cout << "\nvertex: ";
    cin >> v;
    cout << "\nadjacent: ";
    cin >> w;
    vertices[v]->push_back(w);
}

无论这是否是填充我介绍的数据结构的正确方法，我都需要帮助!如果不是，执行任务的正确方法是什么？

Answer 1

我建议使用 std::vector<std::vector>对于 adjacency matrix你的图表，我建议你不要将 UI 与你的类混合使用(参见下面的代码):

class Graph
{
public:
  Graph(std::size_t const n_vert) : adjmat(n_vert, std::vector<int>(n_vert)) {}
     // Member functions for Graph class
     void addEdge(std::size_t const from, std::size_t const to, int const weight);
     void print();
     void type(std::string);
private:
     std::vector<std::vector<int>> adjmat;
};

void Graph::addEdge(std::size_t const from, std::size_t const to, int const weight = 1)
{
  // or `adjmat.at(from).at(to)` for range checking
  adjmat[from][to] = weight;
}

int main ()
{
    Graph G(10);
    int v, w;
    std::cout << "\nvertex: ";
    std::cin  >> v;
    std::cout << "\nadjacent: ";
    std::cin  >> w;
    G.addEdge(v, w);

    return 0;
}

不过，对于小型图，建议使用此解决方案。