最大流算法中的Edmonds-Karp算法为什么用广度优先搜索增广路径
发布网友
发布时间:2022-04-29 18:47
我来回答
共1个回答
热心网友
时间:2022-06-19 18:30
我花了三个晚上,画了无数的图,试图构造出一个深度遍历之后复杂度会超过ve²,没能成功
然后用了一下午的时间google,最后发现有个国外的论文,研究员通过递归方式构造了一个图,(也就是教科书上那个傻傻的证明e|f|复杂度的五边棱形图,他把这个大棱形对角线那一条边替换成一个小棱形,然后把小棱形的对角线又替换,迭代n次,每个外层大棱形四边的流量,都是内层小棱形四边流量的两倍,也就是说,最里面的小棱形对角线游戏是1,四边流量是1,外面一层的棱形是2,再外面是4,8,16……)
作