图表示——链表的链表
Graph Representation - Linked List of Linked Lists
我知道邻接表是表示图的常用数据结构，使用链表数组。我正在为 C 中的简单搜索引擎实现倒排索引，并且打算使用邻接表。但是，我发现使用邻接表的一个缺点是，如果您不知道倒排索引中将包含多少个词，则必须假设索引中有任意多的词（数组元素）以创建邻接表。这可能会导致使用过多的内存。这不是一个大问题，但我想知道是否有更好的方法来实现它。
我在想解决这个问题的一个方法是创建一个链表的链表来代替我的倒排索引。我还没有看到很多链接列表图形表示的链接列表的例子，所以我假设它不常用或不常用表示。我想知道用链表的链表来表示一般的图是否合适？还是坚持使用邻接表更好？任何见解将不胜感激。
这两种方法都需要权衡取舍。
您可以使用邻接表而不使用额外的内存，但是每次插入和删除都会花费 O(|V|) 时间。
例如，如果您在第一次添加顶点时将数组的长度加倍，则每次将顶点数加倍时只需花费 O(|V|) 时间。但是，使用这种方法几乎总是会占用额外的内存。
如果您选择用一个 LinkedList 的 LinkedList 来表示一个图，您确实优化了内存，但会牺牲大量的性能。查找给定节点的邻居从 O(|E|) 时间到 O(|V||E|) 时间，这消除了邻接列表的最大优势之一。
而且如果您想执行更高级的操作（例如遍历图形），性能成本将非常低效。对于顶点的每个邻居，您必须重新遍历节点 LinkedList 才能找到相邻的顶点。
我知道邻接表是表示图的常用数据结构，使用链表数组。我正在为 C 中的简单搜索引擎实现倒排索引，并且打算使用邻接表。但是，我发现使用邻接表的一个缺点是，如果您不知道倒排索引中将包含多少个词，则必须假设索引中有任意多的词（数组元素）以创建邻接表。这可能会导致使用过多的内存。这不是一个大问题，但我想知道是否有更好的方法来实现它。
我在想解决这个问题的一个方法是创建一个链表的链表来代替我的倒排索引。我还没有看到很多链接列表图形表示的链接列表的例子，所以我假设它不常用或不常用表示。我想知道用链表的链表来表示一般的图是否合适？还是坚持使用邻接表更好？任何见解将不胜感激。
这两种方法都需要权衡取舍。
您可以使用邻接表而不使用额外的内存，但是每次插入和删除都会花费 O(|V|) 时间。
例如，如果您在第一次添加顶点时将数组的长度加倍，则每次将顶点数加倍时只需花费 O(|V|) 时间。但是，使用这种方法几乎总是会占用额外的内存。
如果您选择用一个 LinkedList 的 LinkedList 来表示一个图，您确实优化了内存，但会牺牲大量的性能。查找给定节点的邻居从 O(|E|) 时间到 O(|V||E|) 时间，这消除了邻接列表的最大优势之一。
而且如果您想执行更高级的操作（例如遍历图形），性能成本将非常低效。对于顶点的每个邻居，您必须重新遍历节点 LinkedList 才能找到相邻的顶点。