algorithm - 找出图中给定节点对之间的最大距离

Question

有 N 个节点由 N-1 条边连接。每条边的权重为 1，可以从任何其他节点到达任何节点。

我们得到了一个节点子集。我们需要对节点子集进行配对（1 对 1 映射）并找到配对后可能的最大距离。

For example:
N = 8 ( Number of nodes) 
subset of nodes = [2,4,5,6]

Graph: 

   7
   |
6--1--2--8 
   | 
   3--4
   | 
   5

Solution
Maximum distance: 
    Pairs
    (2,4) : 2-1-3-4 => distance 3 
    (6,5) : 6-1-3-5 => distance 3 
    max distance = 3+3 = 6
    It's possible to form other pairs but max distance will always comes out to 6.

如何计算最大距离？

标签： algorithmgraph-theory

Answer 1

首先找到树的质心。接下来对每对顶点执行以下操作： 找到顶点与树形心之间的距离。这些值的总和是顶点之间的最大距离。