由于Kruskal算法是贪婪的方法，这意味着我们有时可能无法获得真正的最小路径。
但是，任何人都可以提供一个案例，表明这个算法没有达到最低限度吗？
我不是在寻找复杂性，只需要一个真正没有得到最佳解决方案的案例。
谢谢
我认为Kruskal的算法总能找到最佳解决方案。它甚至可以与具有负边缘成本的图形一起使用。有一个关于Kruskal贪婪算法的最优性的证明来自教科书，名为算法设计：考虑由Kruskal算法添加的任何边e =（v，w），并且让S是v在其中具有路径的所有节点的集合。就在添加e之前的那一刻。显然v∈S，但是w̸∈S，因为添加e不会产生循环。此外，还没有遇到从S到V-S的边缘，因为任何这样的边缘都可以在不创建循环的情况下添加，因此可以通过Kruskal的算法添加。因此，e是最便宜的边缘，其中一端在S中，另一端在V-S中，因此它属于每个最小生成树。因此，如果我们能够证明Kruskal算法的输出（V，T）实际上是G的生成树，那么我们就完成了。显然，（V，T）不包含循环，因为算法是明确设计的，以避免创建循环。此外，如果（V，T）未连接，那么将存在节点S的非空子集（不等于V的全部），使得从S到V-S没有边缘。但这与算法的行为相矛盾：我们知道，由于G是连通的，S和V-S之间至少有一条边，算法会添加它遇到的第一条边。