我试图找到一种检测给定图G是否具有两个不同的最小生成树的有效方法.我也试图找到一种方法来检查它是否有3种不同的最小生成树.我现在的天真解决方案是运行Kruskal算法一次并找到最小生成树的总重量.稍后,从图中移除边缘并再次运行Kruskal算法,并检查新树的权重是否是原始最小生成树的权重,对于图中的每个边都是如此.运行时是O(| V || E | log | V |),这根本不是很好,我认为有更好的方法.
任何建议都会有所帮助,在此先感谢
algorithm graph minimum-spanning-tree graph-algorithm
algorithm ×1
graph ×1
graph-algorithm ×1
minimum-spanning-tree ×1