0

I've got a graph (or unrooted tree) of N nodes and N-1 connections. Each connection has a distance of 1.

How can i find a node v that has the maximum distance between v and a set of nodes E{}, when v can be a node in E?

Constraints:

  • (N <= 50000)
  • Number of node in E <= N
  • Time limit 1 s
4

3 回答 3

1

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

编辑：

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

好的，现在我了解您的指标了。E对于每条边，您想要计算从该边到该边任一侧的元素的距离总和。您可以通过计算从叶子到根的值来做到这一点（稍微挥手）。

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

于 2012-09-15T22:45:38.213 回答
0

这是一个简单的算法来计算每个节点到 的每个顶点的距离E。

该图是一棵树，最初是无根的。

  1. 任意选择一个节点作为根

  2. 遍历树，并为每个节点计算其子树中的顶点数E（我们可以调用此函数e(node)）。

    • 例如，如果您的树如下（其中括号显示 中的顶点E={C,D,I}），您将计算如下所示的数字：

      vertices in the graph:              e(v)

          A                          3
         / \                        / \
        B  (C)                     1   2
       / \   \                    / \   \
     (D)  F   G                  1   0   1
     /         \                /         \
    H          (I)             0           1
  3. 还要计算根节点与集合的距离E（调用此函数d(v)）。我们看到d(A)=6，并且在步骤 2 中遍历树时很容易计算出来。

  4. 然后，再次遍历树，计算每个节点的距离函数，公式为d(v) = d(parent(v)) + size(E) - 2*e(v)。这将花费O(n)所有节点的时间，因为它是每个节点的恒定时间。

    该公式是通过考虑当您从父级移动到子级时得出的，与节点集的距离E变化如下：

    • E 不在子树的子树中的每个节点的距离增加 1
    • 每个节点的距离减少 1，E其中每个节点也位于子节点的子树中

    例子：

    • 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
  5. 然后只需搜索v具有最高的节点d(v)，您可以通过再次遍历树来做到这一点。您也可以在步骤 4 中遍历树的同时执行此操作。

该算法只需要对树进行 2 次不同的遍历，每次都需要O(n)时间。因此，整体算法复杂度为O(n)。

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

于 2012-09-18T13:13:16.197 回答
0

如果图形是非循环的，您可以将边权重设为 -1 并运行 Floyd-Warshall。这将为您提供所有对最长的路径。然后对于图中的每个节点，取到 E 中节点的平均距离。

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

于 2012-09-15T23:33:34.577 回答