Ash*_*hot 2 algorithm graph minimum-spanning-tree
这是查找最小生成树的正确算法.
将Graph划分为2个相同连接的部分.找到它的最小生成树.使用连接它们的最小边缘连接它们.我试图得到这个算法的反例,但不能.
考虑一个四边形图,以正方形连接,左边缘成本为10,所有其他边缘成本为1.如果将图形左右分割为递归步骤,最终将生成一个生成树费用12,而不是费用3.
MST不适合"分而治之"的算法.最接近的可能是反向删除算法; 无论何时删除边缘(因为它会断开图形),您可以将剩余的步骤视为在该边缘的两侧递归执行.