c - 图表示——链表的链表

Question

我知道邻接表是表示图形的常用数据结构，它使用链表数组。我正在为 C 中的简单搜索引擎实现倒排索引，并且打算使用邻接表。但是，我发现使用邻接表的一个缺点是，如果您不知道倒排索引中将包含多少个词，则必须假设索引中有任意多的词(数组元素)以创建邻接表。这可能会导致使用过多的内存。这不是一个大问题，但我想知道是否有更好的方法来实现它。

我在想解决这个问题的一个方法是创建一个链表的链表来代替我的倒排索引。我还没有看到很多链接列表图形表示的链接列表的例子，所以我假设它不常用或不常用表示。我想知道用链表的链表来表示一般的图是否合适？还是坚持使用邻接表更好？任何见解将不胜感激。

Answer 1

这两种方法都需要权衡取舍。

您可以在不使用额外内存的情况下使用邻接表，但是，每次插入和删除都将花费 O(|V|) 时间。

例如，如果您在第一次添加顶点时将数组的长度加倍，则每次将顶点数加倍时只需花费 O(|V|) 时间。但是，使用这种方法几乎总是会占用额外的内存。

如果您选择用 LinkedLists 的 LinkedList 来表示一个图，您确实优化了内存，但是性能上有很大的权衡。查找给定节点的邻居从 O(|E|) 时间到 O(|V||E|) 时间，这消除了邻接列表的最大优势之一。

如果您想进行更高级的操作(例如遍历图形)，性能成本将非常低效。对于顶点的每个邻居，您必须重新遍历节点 LinkedList 才能找到相邻顶点。