相关疑难解决方法(0)

我正在帮助一个与工作相关的项目的朋友,他需要计算从节点a到节点b的最大容量,其中边缘具有容量.然而,从a到b的路径中的最大容量受到具有最低容量的边缘的限制.

让我试着用一个简单的样本来解释

因此,图是带有加权边的有向图,它可以是循环的.容量最大的路径为s-> b-> t,容量为250,因为该边缘设置了限制.

我做了一些阅读,发现这类问题是"最广泛的路径问题",或者我称之为最小容量最大的路径,但我没有找到任何示例或任何伪代码解释如何解决这个问题.

我正在考虑使用BFS找到从s到t的所有路径,并且某种方式只允许在路径中访问一个节点,然后在路径中找到最小值,这是否有效？

在最坏的情况下,我们可以通过使用Kruskal算法找到O(E log*V)中的最小瓶颈生成树.这是因为每个最小生成树都是生成树的最小瓶颈.

但是我在这个课程中遇到了这个面试问题.

即使在最坏的情况下,我们如何才能在线性时间内找到最小的瓶颈生成树.请注意,我们可以假设在最坏的情况下我们可以计算线性时间内n个键的中位数.