我的任务是这样的，给定图G中与E道路连接的V个村庄，每条道路都标有一个正数。而且您必须至少达到此数字的水平才能进入这条道路。换句话说，如果一条道路标记为 5，那么您的等级必须至少为 5 或更高才能进入这条道路。现在我的任务要求设计年鉴，找到能够从任何其他村庄到达V中的任何村庄所需的最低净空水平。所以，我的解释是，我们可以在图表中找到最大权重边缘。但是我还没有弄清楚哪种算法适合这种情况。
这可以在O(E)中解决。
为什么你的解决方案是错误的？考虑一个三角形，其中两条边是 1，最后一条是 2，所需的最低间隙是 1，您的解决方案说 2。
我能想到的解决方案是创建最小瓶颈生成树 (MBST(，而不是采用它的最大边缘，这将是您的间隙级别。
为什么它会起作用？那么这棵树的最大边缘是你能得到的最小边缘(最小瓶颈(，并且仍然到达图中的任何地方(跨越(。
MBST可以使用分而治之方法在O(E)中创建，而不是越过该树中的所有边缘以找到最大值O(E)。总共O(E)
.您可以使用一个简单的MST来解决它，因为任何MST都是MBST的(在 q3 中证明(，但这需要O(E log V)或O(E + V log V)，具体取决于算法(Kruskal 或 Prim(。