graph - 在图中找到访问次数最多的节点

Question

图中有 N 个节点，由 N-1 条边连接。从一个节点到任何其他节点恰好有 1 条最短路径。节点从 1 到 N 编号。给定 Q 个查询，它们告诉源节点和目标节点。在经过这些 Q 条路径后找到访问次数最多的节点。例如，假设 Q=3 和 3 个查询是：

1 5

2 4

3 1

所以从节点 1 到节点 5，然后从节点 2 到节点 4，然后从节点 3 到节点 1。最后，在 Q 次查询之后找到访问次数最多的节点。找到每条路径并增加每个访问的节点计数是一种幼稚的方法。面试官让我优化一下。

标签： graphtreeleast-common-ancestor

Answer 1

优化通常涉及权衡；在某些情况下，一种算法明显优于另一种算法，但在另一些情况下，一种算法在某个方面（例如时间）更好，而另一种算法在不同方面（例如内存使用）更好。

在您的情况下，我猜您的面试官正在寻找一种方法来优化您开始接收查询后必须完成的处理量，即使这意味着您必须对图表进行更多预处理。我这么说的原因是“查询”这个词；为“在线”查询优化数据源是很常见的。（当然，（s）他可能不希望您自己决定这种权衡是可以的；相反，（s）他可能希望就不同类型的权衡进行对话。）

所以，考虑到这一点。. .

• 我看到您已经用 [tree] 和 [least-common-ancestor] 标记了您的问题，因此您可能已经做出了最大的观察，即：
  • 图是一棵树。我们可以任意选择一个“根”，这样每个其他节点都有一个“父”、一个非零“深度”、一个或多个“祖先”等。
  • 一旦我们这样做了，从节点a到节点b的最短路径包括节点a、节点b、不是 b 的祖先的 a 的所有祖先、不是 a 的祖先的b的所有祖先，以及它们的“最不共同的祖先”。（如果a是b的祖先，反之亦然：如果a是b的祖先，那么它是a和b的最小共同祖先，反之亦然。如果a和b相同，它仍然是正确的。 )
• 因此，我们可以进行以下预处理：
  • 将图表示为从每个节点到其邻居列表的映射。（由于节点从 1 到N编号，因此此映射是N个列表的数组。）
  • 选择一个根节点。
  • 计算并存储每个节点的“父节点”和“深度”。（我们可以使用深度优先搜索或广度优先搜索在O ( N ) 时间内完成此操作。）
  • 对于每对节点，计算并存储它们的“最小共同祖先”。（我们可以使用上一步和记忆化的结果在总时间O ( N ² ) 内完成此操作，因为记忆化提供了摊销。）
  • 初始化从每个节点到它是路径端点的次数的映射，以及从每个节点到它是路径端点的最小共同祖先的次数的映射。（注意：如果给定的路径是从单个节点到它自己，那么我们将把它算作它是路径端点的两倍——以及它是端点的最后一个共同祖先的两倍。）
• 对于每个查询，更新两个映射。我们可以在每个查询O (1) 时间内完成此操作，总共需要O ( Q ) 时间。
• 最后：
  • 对图进行后序遍历，计算访问该节点的路径数。其逻辑如下：访问节点a的路径总数等于访问其每个子节点的路径数之和，减去其每个子节点最后一次的次数之和路径端点的共同祖先，加上a本身是端点的次数，减去a本身是路径端点的最后一个共同祖先的次数（以消除重复计算）。
  • 返回上一步返回最大数字的节点。如果多个节点并列最大，则 . . . 我不知道，问题陈述对此含糊不清，您需要询问要求。

总体而言，这需要O ( N ² ) 预处理，每个查询O ( Q ) 实时处理和O ( N ) 后处理。

如果N非常大，并且我们预计即使只有一小部分节点被访问过一次，那么我们可以通过忽略树中未访问的部分来加速后处理。这涉及维护一组作为路径端点的节点，然后以“自下而上”的方式进行后处理，从最深的此类节点开始，并且仅当访问的路径数量为该节点小于它是最不共同祖先的次数。如果我们用P表示不同端点的数量，用M表示不同访问节点的数量，那么这可以用类似O ( P  log  P  +  M）。