嵌套列表以在 C++ 中实现邻接列表

Question

我正在 this website.
上查看拓扑排序代码除了邻接列表的声明（第 15 行）之外，我理解代码的一部分，即

list<int> *adj;

基本上，对我来说，adj 应该是一个指向整数列表的指针，但在这种情况下，根据他们如何使用它，它是一个列表列表......所以列表列表不应该是

list <list<int> > adj;

谁能给我解释一下吗？

Answer 1

您也可以这样做，但是本网站创建的是一个列表数组，而不是一个列表列表。我认为这种方法（列表数组）是许多编程语言中表示邻接列表的常用方法。通过这种方式，顶点从 0 到 V-1 编号，您可以使用索引运算符 adj[i]

直接访问相邻列表

我不太清楚确切的原因，但我想这是为了提高效率。

编辑：请注意，根据 C++ 参考，列表是双链表，因此如果您想要访问元素 i，则需要通过链接节点进行迭代，直到到达元素 i。使用数组，您可以直接访问您感兴趣的列表，无需迭代，因此效率更高。在www.cplusplus.com中我们可以读到：

The main drawback of lists and forward_lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list, one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).

Answer 2

重要的是要注意，您链接到的代码相当单一。它有一个突出的问题就是你提到的那个成员，list<int> *adj。

在现代 C++ 中，我们倾向于避免使用 new and delete directly，相反，我们可以使用智能指针（例如 std::unique_ptr）或容器。在这种特定情况下，而不是：

list<int> *adj;
// ... etc. ...
Graph(int V) {
    adj = new std::list<int>[V]; 
}

确实会更好用：

std::vector<std::list<int>> vertex_adjacencies;
// ... etc. ...
Graph(std::size_t num_vertices) : vertex_adjacencies(num_vertices) { }

现在，至于你对列表列表的建议 - 这也是可能的：

std::list<std::list<int>> vertex_adjacencies;
// ... etc. ...
Graph(std::size_t num_vertices) : vertex_adjacencies() 
{
    auto empty_adjacencies = std::list<int>{};
    std::fill_n(
        std::front_inserter(vertex_adjacencies), 
        num_vertices,
        empty_adjacencies);
}

但这需要重写其他各种方法。另请注意，该图旨在具有固定数量的顶点，不会添加或删除顶点，因此将特定于顶点的邻接放置在列表中没有多大意义。（并不是说每个顶点的邻接一个单独的 std::list 是一个好主意，无论如何，性能方面，但没关系）。

嵌套列表以在 C++ 中实现邻接列表

nested lists to implement adjacency lists in c++

c++

pointers

stl

graph-theory

list