双向图算法

Question

我有一个N nodes和N-1 connections的图表(或无根树)。每个连接都有一个distance of 1。

当v可以是EE 212中的节点时，如何找到v与一组节点E{}之间最大距离的节点v？

Constraints:

• (N <= 50000)
• E <= N中的节点数
• 时限1 s

Answer 1

我将使用宽度优先搜索，从节点集E开始。然后，v将是您访问的最后一个节点。

编辑：

1-2-3-4    E={1,4,5}
    |
    5

好了，现在我明白你的标准了。您需要为每一条边计算从该边到该边两侧的E元素的距离的总和。您可以通过计算从叶子到根的值(稍微挥手)就可以做到这一点。

然后，您可以为每个节点计算每个传入边缘上这些值的总和。选择具有最大和的节点。

Answer 2

如果图形是无圈的，你可以使边的权重-1和运行弗洛伊德-华尔.这将给你所有对最长的路径。然后，对于图中的每个节点，取E中节点的平均距离。

否则，我相信看一个NP-完全问题，试图在任意图中找到最长的路径。

Answer 3

这里有一个简单的算法来计算每个节点与E的每个顶点之间的距离。

这张图是一棵树，最初是没有根的.

1. 任意选择一个节点作为根
2. 遍历树，并计算每个节点在E中的子树中的顶点数(我们可以调用这个函数e(node))。

图中的

- For example, if your tree is as follows (where the brackets show the vertices in `E={C,D,I}`), you will compute the numbers as shown:

顶点: e(v) A3/\B (C) 1 2/\ (D) F1 0 1/\H (I) 0 1

​

1. 还计算根节点与集合E的距离(调用此函数d(v))。我们看到d(A)=6，并且在步骤2中遍历树时很容易计算。
2. 然后，再次遍历树，计算每个节点的距离函数，其中公式为d(v) = d(parent(v)) + size(E) - 2*e(v)。这将占用所有节点的O(n)时间，因为每个节点的时间都是恒定的。 该公式的推导考虑到，当您从父节点移动到子节点时，E中的节点集之间的距离通过以下方式进行更改：

- an increase in distance by 1 for each nodes in `E` _not_ in the subtree of the child
- a decrease in distance by 1 for each node in `E` which is also in the subtree of the child  

示例：

- `d(B) = d(A) + size(E) - 2*e(B) = 6 + 3 - 2 = 7`,
- `d(D) = d(B) + size(E) - 2*e(D) = 7 + 3 - 2 = 8`,
- `d(H) = d(D) + size(E) - 2*e(H) = 8 + 3 - 0 = 11`,
- `d(F) = d(B) + size(E) - 2*e(F) = 7 + 3 - 0 = 10`

​

1. 然后，只需搜索具有最高v的节点d(v)，就可以通过再次遍历树来做到这一点。您还可以在步骤4中遍历树的同时执行此操作。

该算法只需要两个不同的遍历树，每一个需要O(n)时间。因此，总的算法复杂度是O(n)。

请注意，此算法之所以如此高效，是因为该图是一个树。大多数最短路径算法都是针对一般图的。树要简单得多，因为在任意一对顶点之间只有一条唯一的路径。因此，在最短路径算法中不需要一般需要的策略。