algorithm - 一棵树的中心点？

Question

假设我们有一棵有根有序树。对于每个节点，我们都有一个子节点链表。 P[i] 是节点 i 到所有其他节点的距离之和。有没有一种算法可以找到树中具有最小 P[i] 的节点之一(可能是几个相等的 P[i])，在最坏的情况下花费 O(n) 时间？

Answer 1

这是一些有效的 O(N) 代码。在此示例中，我使用图表 {0:[1,2,3],1:[4,5],2:[6]}

我编写代码是为了好玩。对于下图，它发现中心是节点 0，其 P[i] 值为 9。从 i->P[i] 的映射是 {0: 9, 1: 10, 2: 12, 3: 14, 4:15, 5:15, 6:17

nodes={0:[1,2,3],1:[4,5],2:[6]}
PB={}
NB={}
def below(i):
    if i not in nodes:
        PB[i]=0
        NB[i]=1
        return 0,1
    tot_nodes_below=0
    tot_paths_below=0
    for node in nodes[i]:
        paths_below,nodes_below=below(node)
        tot_nodes_below+=nodes_below
        tot_paths_below+=paths_below
    tot_paths_below+=tot_nodes_below
    tot_nodes_below+=1
    PB[i]=tot_paths_below
    NB[i]=tot_nodes_below
    return tot_paths_below,tot_nodes_below

P={0:below(0)[0]}
def fill_P(i):
    for node in nodes[i]:
        P[node]=P[i]+7-2*NB[node] #7 is the number of nodes
        if node in nodes:
            fill_P(node)
fill_P(0)

_min=min(P.values())
answers=[k for k in P if P[k]==_min]
print answers
"[0]"

解释: 这段代码是 O(N)(我觉得对吧？)

基本上 nodes = dict 显示每个父节点连接到它的子节点。

令 T[i] 为“树 i”。我将其定义为从节点 i 开始的子树。 (例如 T[2]=2:6，而 T[0] 是整棵树，T[1] 将是 1:[4,5]。)

现在NB[i]是T[i]中的节点数。

NB={0: 7, 1: 3, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1}

PB[i] 是 T[i] 内节点到 i 的距离之和。 (所以 PB[i] 基本上就是 P[i]，除非我们只看 T[i] 而不是 T[0]。

PB={0:9, 1:2, 2:1, 3:0, 4:0, 5:0, 6:0}

看到 PB[0]=9 因为在 T[0] 中有 9 条路径到 0。 PB[6]=0 当 NB[0]=1 等

因此，要实际构建 PB 和 NB，我们需要递归 O(N) 函数“below(i)”。

below(i) 从根节点开始，沿着每个子树 T[i] 向下移动。对于每个子树，它计算出 NB[i] 和 PB[i]。注意递归的基本情况是微不足道的，如果节点没有子节点，PB[i]=0 和 NB[i]=1。

为了计算具有子节点的节点的 PB[i] 和 NB[i]，我们使用递归公式。 令节点 i 有子节点 x1..xj 然后 NB[i]=1+sum(NB[x])。

有一个类似的递归公式来计算 PB[i]。

PB[i]=SUM(PB[x])+NB[i] 我们添加 NB[i] 的原因是因为下面的每个节点都必须经过额外的距离 1 才能从子树 T[x] 到达节点 i.

一旦我们下面的函数 (i) 填充了 NB 和 PB，我们就可以使用这两个结果来找出 P。

fill_P(i) 使用 NB 和 PB 来做到这一点。

这个想法是，如果节点 i 和 j 彼此靠近，P[i] 将接近 P[j] 的值。

事实上，让我们看看是否可以使用 NB[1]、PB[1] 和 P[0] 计算出 P[1]。

结果是 P[1]=P[0]+7-2*NB[1] (我们甚至不需要使用 PB 的结果，但是我们需要 PB 来获得初始 P[0] 值)。 要了解为什么这个公式是正确的，请考虑为什么 P[1] 不等于 P[0]。有一张树的照片会很有帮助。让我们通过删除节点 1 将树分成两部分。现在这给出了树的左侧(不包括节点 0)和树的右侧，其中包括节点 0)。请注意，树的左侧只是 T[1]，我们为此得到了结果 NB[1]。 P[1] 与 P[0] 相同，除了从 T[1] 中的节点的所有路径行进距离少 1。来自不在 T[1] 中的节点的所有路径进一步行进 1(通过节点 0 到达节点 1)。路径的数量分别为 NB[1] 和 7-NB[1]。所以我们有 P[1]=P[0]+(7-NB[1])-NB[1]，它给出了我们需要的公式。

现在我们有了 P[0] 和 P[1] 的正确 P 值。我们可以计算节点 1 或节点 0 的任何子节点的值。fill_P 只是应用此公式遍历每个子节点，我们得到结果 P。我们只是迭代 P 以找到最小值，这就是我们的结果。 .

希望这是有道理的，现在干杯。