图形表示-链表的链表

Question

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

我在想，这个问题的一个解决方案是创建一个链表的链表来表示我的倒排索引。我还没有见过链表的链表图形表示的许多示例，所以我假设它不是常用的或常规的表示。我想知道使用链表的链表来表示图形是否合适？还是坚持使用邻接表更好？任何真知灼见都将不胜感激。

Answer 1

这两种方法都需要权衡。

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

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

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

如果你想做一个更高级的操作--比如遍历图表--性能成本将会非常低。对于顶点的每个邻居，您必须重新遍历节点LinkedList才能找到相邻的顶点。