c++ - 来自Geeks for Geeks网站的有关BFS的代码

Question

我想问他为什么将list<int> *adj视为邻接列表数组。我认为这只是一个动态数组，而不是列表数组？有人可以解释一下吗？

// Program to print BFS traversal from a given 
// source vertex. BFS(int s) traverses vertices  
// reachable from s. 
#include<iostream> 
#include <list> 
  
using namespace std; 
  
// This class represents a directed graph using 
// adjacency list representation 
class Graph 
{ 
    int V;    // No. of vertices 
  
    // Pointer to an array containing adjacency 
    // lists 
    list<int> *adj;    
public: 
    Graph(int V);  // Constructor 
  
    // function to add an edge to graph 
    void addEdge(int v, int w);  
  
    // prints BFS traversal from a given source s 
    void BFS(int s);   
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 

Answer 1

I want to ask why he considers list<int> *adj; is an array of adjacencylists ....

它不是数组，而是指向 list<int>的指针。指针不是数组。

I think this is only a dynamic array but not array of lists ?

它不是动态数组。
作者试图说，但非常笨拙的是，指针最终将指向内存中的一个区域，该区域将包含 std::list<int>对象的连续缓冲区，因此使用了术语“动态数组”。
在示例中，使用以下行创建缓冲区: adj = new list<int>[V];在 Graph构造函数中。这将在连续内存中创建 V std::list<int>对象，并且 adj将指向列表中的第一个对象。

代码的问题在于，作者本可以为工作使用更好的工具 std::vector<std::list<int>>。 std::vector的用法将

摆脱原始指针的使用。

使动态数组更易于处理。

使您编写的代码更小并且更不易出错。

无需new[]和delete[]

现在，该 Graph类存在内存泄漏。如果您在玩具程序中以外的任何地方使用它，则在编写适当的复制语义之前，通过编写用户定义的复制构造函数，用户定义的赋值运算符和析构函数，它很快就变得无法使用。
这是 Graph类的重写:

#include <iostream> 
#include <list> 
#include <vector>

class Graph 
{ 
   std::vector<std::list<int>> adj;    

public: 
    Graph(int V); 
    void addEdge(int v, int w);  
    void BFS(int s);   
}; 
  
Graph::Graph(int V) : adj(V) {}
 
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); 
    // and if you want to add some debugging for boundary conditions, 
    // replace previous line with
    // adj.at(v).push_back(w);
} 

整个类可以在任何上下文中安全使用。请注意，不需要 V成员变量，因为 adj.size()知道 V是什么。