图表示为邻接表，表示为二叉树，可能吗？

Question

首先道歉，英语不是我的第一语言。

这是我对图的理解，它表示为形容词列表：它通常用于稀疏图，这是大多数图的情况，它使用V（顶点数）列表。因此，对于无向图，V个头指针+2e个（边数）节点。因此，空间复杂度=O(e+V)，因为任何节点可以有多达V-1条边（不包括自身），所以检查节点邻接的时间复杂度为O(V)。

我想知道的是，有没有可能将列表（边缘节点）变成二叉树？因此，要确定A节点是否与B节点相邻，时间复杂度为O(logn)，而不是线性O(n)。如果可能的话，是否经常这样做呢？还有，那种数据结构叫什么？我一直在谷歌搜索这样的组合是否可能，但没有找到任何东西。如果有人能给我详细解释这一点，我将非常感激，因为我是数据结构的新手。谢谢你。

编辑：我知道可以对数组执行二进制搜索。我说的是链表表示法，我想当我说到列表的头时，我已经说得很清楚了，但是哇哦

Answer 1

没有理由每个顶点的邻接列表不能存储为二叉树，但是有一些折衷。

正如您所说的，这种邻接列表表示经常用于稀疏图。通常，“稀疏图”意味着一个特定的顶点与少数其他顶点相邻。所以你的“邻接列表”对于一个特定的顶点将是非常小的。当然，二分搜索是O(logn)，而顺序搜索是O(n)，当n很小时，顺序搜索更快。我见过这样的情况：当n小于16时，顺序搜索胜过二分搜索。当然，这取决于实现，但不要指望二进制搜索对小列表更快。

另一个要考虑的是记忆。链表开销是每个节点一个指针。当然，除非您使用的是双链表。二叉树开销是每个节点两个指针。也许没什么大不了的，但是如果您试图表示一个非常大的图，那么这个额外的指针就变得很重要了。

所以，是的，您可以使邻接列表为二叉树。您必须根据应用程序的速度要求和数据的性质来决定是否值得付出额外的努力。