这是一种寻找最小生成树的正确算法吗？
将图分成两个相等连接的部分。找到它们的最小生成树。使用连接它们的最小边将它们连接起来。我尝试得到这个算法的反例，但无法找到。
2个回答
6
考虑一个由四个节点组成的图形，呈正方形相连，左边的边缘成本为10，其他所有边缘成本均为1。如果您将图形分为左侧和右侧进行递归步骤，则最终生成的生成树成本为12，而不是3。
最小生成树算法不适用于“分而治之”算法。最接近的可能是反向删除算法；每当您无法删除边缘（因为它会断开图形）时，您可以将其余步骤视为在该边缘两侧上递归执行。
最小生成树算法不适用于“分而治之”算法。最接近的可能是反向删除算法；每当您无法删除边缘（因为它会断开图形）时，您可以将其余步骤视为在该边缘两侧上递归执行。
- Sneftel
1
您描述了一种分治算法，该算法在确定MST时不起作用。Sneftel提供了一个很好的反例，递归地将图形分成两个连接部分将非常昂贵。
相反，找到MST的好方法是使用Prim算法等贪心算法。我们知道贪心算法会起作用，因为这个问题表现出最优子结构。对于这个算法，您将希望将图表示为邻接列表。首先，从任意节点开始并将其添加到已访问列表中。将此节点的所有边缘添加到最小堆中。将最便宜的边缘包括在您的MST中，并将连接节点添加到已访问列表中。从该节点添加所有边缘到您的最小堆，然后选择到尚未访问的节点的最便宜的边缘。继续这样做，直到所有节点都被访问。完成后，您就有了MST。
您可以使用其他数据结构来存储图形和已访问的边缘，但我上面概述的数据结构将最大化运行时间。如果我们使用这些数据结构分析运行时间，我们可以看到运行时间为O（E log V），这是更新元素成本并在删除边缘后维护堆的时间。更具体地说，O（log V）修复堆，并且这样做E次。
我还发现了一个快速的2分钟视频，用一个例子概述了Prim算法：2分钟内学会Prim算法。
希望这些信息对你有所帮助！
相反，找到MST的好方法是使用Prim算法等贪心算法。我们知道贪心算法会起作用，因为这个问题表现出最优子结构。对于这个算法，您将希望将图表示为邻接列表。首先，从任意节点开始并将其添加到已访问列表中。将此节点的所有边缘添加到最小堆中。将最便宜的边缘包括在您的MST中，并将连接节点添加到已访问列表中。从该节点添加所有边缘到您的最小堆，然后选择到尚未访问的节点的最便宜的边缘。继续这样做，直到所有节点都被访问。完成后，您就有了MST。
您可以使用其他数据结构来存储图形和已访问的边缘，但我上面概述的数据结构将最大化运行时间。如果我们使用这些数据结构分析运行时间，我们可以看到运行时间为O（E log V），这是更新元素成本并在删除边缘后维护堆的时间。更具体地说，O（log V）修复堆，并且这样做E次。
我还发现了一个快速的2分钟视频，用一个例子概述了Prim算法：2分钟内学会Prim算法。
希望这些信息对你有所帮助！
- Emilio Amaya
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接