到达图中具有连通分量的每个节点的最短时间

Question

考虑一个没有循环的图。该图有 K 个不同的对，每个 other.if 我们要向所有人发送一封信。发送一封信需要一个单位时间。我们想加快这一进程。那么这封信到达每个人的最短时间是多少（图的节点）。我们可以把信交给所有连通分量中的任何一个连通分量

Answer 1

使用动态规划来解决这类问题陈述。

Answer 2

他们的关键点是图形没有循环。因此，图表的每个组成部分都是一棵树。有关详细信息，请参阅维基百科：https://en.wikipedia.org/wiki/Tree_(graph_theory)

让我们在下文中假设，您的图表只有一个组件和 n 个节点。如果你的图有多个组件，只取最大的一个并将 n 设置为该组件的节点数。

最坏的情况是，信件的传递从叶节点（底部）向上到根节点（顶部），然后向下到另一个叶节点。此路径的长度为 (n-1)。因此，这次交付需要 (n-1) 时间。

换句话说：具有 n 个节点的树中最长的路径长度为 n-1。