algorithm - 在图 G 中找到最大权重边？

Question

我的任务是，给定图 G 中与 E 条道路相连的 V 个村庄，每条道路都标有正数。而且你必须至少达到这个数字的级别才能访问这条路。换句话说，如果一条道路标记为 5，那么您的等级必须至少达到 5 或更高才能进入这条道路。现在我的任务要求设计算法，找到能够从任何其他村庄到达 V 中的任何村庄所需的最低限度。所以，我的解释是我们可以在图中找到最大权重边。但是我还没有弄清楚哪种算法适合这种情况。

Answer 1

这可以在 O(E) 中解决。

为什么你的解决方案是错误的？考虑一个三角形，其中两条边为 1，最后一条边为 2，所需的最低间隙为 1，您的解决方案为 2。

我能想到的解决方案是创建 Minimum bottleneck spanning tree (MBST)，而不是取它的最大优势，这将是您的许可级别。

为什么会起作用？好吧，这棵树的最大边是您可以获得的最小边(最小瓶颈)并且仍然可以到达图中的任何地方(跨越)。

MBST 可以是 created in O(E)使用分而治之的方法，而不是遍历该树中的所有边来找到最大值是 O(E)。总计 O(E)。

您可以使用简单的 MST 来解决它，因为任何 MST 都是 MBST ( proof in q3 )，但这需要 O(E log V) 或 O(E + V log V)，取决于算法(Kruskal 或 Prim)。