我有一个无向连通图，G。我希望能够找到，如果有至少2个MSTS返回真正的算法。
如果我想看看是否有确切2个MSTS？
Answer 1:
我们可以通过修改克鲁斯卡算法有效地检测出这两种情况。 如果有人能想到一个更简单的方法来描述这一切，请让我知道！
采用Kruskal构建一个用于MST相等重量的边缘的每个排列
克鲁斯卡尔算法通过始终包括连接是迄今建造的森林的不同组件的下边缘最小的构建MST。 每当选择任何这样的最小边缘，即，不论其具有相等的权重的边缘如何排序算法是正确的。
克鲁斯卡可以找到每个MST
此外， 每个 MST可以通过选择某些特定的方式订购每一套等重量的边缘，然后运行的Kruskal算法来产生。 看到这一点，假设有一些MST不能被这种方式生产的。 现在减去一些少量的ε-从在此MST每条边的权重（比任何一对不相等的边权重之间的差小）：这MST现在是独特MST，因此采用Kruskal必须产生这MST当与新的边权运行。 但是，因为我们只至多ε，当边缘被重分类调整的边缘，集的具有重量w_i所有边 - 小量必须出现（以某种顺序）马上集的具有重量w_i边（以某种顺序）前与在两组之间不存在其他边缘。 但是，这是原始的，未经修改的边缘有效的可能的排序，以及克鲁斯卡算法只在乎边缘，而不是他们的特殊权重的排序，所以克鲁斯卡尔算法必须从订货生产的MST为好。 这一点与我们的假设，因此它必须是克鲁斯卡尔算法可以产生每MST。
组件图
调用由采用Kruskal算法构建的森林I> = 0边缘加成后步骤F（i）中，和剩余的要考虑的，且不会产生循环R（i）所述边缘。 （当边缘在步骤中添加I，我们通过用R（I-1的副本开始）和删除刚刚加入边缘与加入相同的一对组件的所有其它边形成R（I）。虽然采用Kruskal算法实际上消除了这些其它边缘“懒惰”，所定义的R（i）本方式简化了证明算法的性能。）我们将分手采用Kruskal算法成一系列块 ，其中的每一个包括边缘添加的序列，其中边缘的相同的权重被添加。 调用I 嵌段限定如果或者i = 0，或在R（i）所述最小权重的边缘大于任何边缘在步骤1中添加..我。
假设一些块限定数目i之后的采用Kruskal算法的边缘添加步骤> = 0已经被执行，在R（I）（即不会产生一个周期即下一个最小的边缘）的最小边缘具有权重w 。 克鲁斯卡尔算法将继续联合起来做别的任何事情之前有在某些方面它们之间的重量-W边所有的树木，即使选择这些相等重量的边缘不同的边缘排序会影响树木生产的东西，它可以在不影响该组中的每个树的顶点 。 使这个更准确：
定义一个新的，未加权的多重图（即，可以具有单个顶点对之间的多个边的图），其由在森林F（I）的每个组件（树）顶点的C（i）中。 在C（i）任何顶点v，调用吨（V）中的树F（i）该对应于诉两个顶点u和v之间创建C中的边缘每当重瓦特边缘中的R的情况下（I）在T（u）的一些顶点和在吨一些顶点之间（v）。 调用C（I）I的步骤后的组件图 。
引理：假设对于一些块限定编号i，C（i）具有含有至少1个边缘k个分量（即组件不是单个顶点），并且这些部件中总共有M> = 2K顶点。 称这组顶点M的那么不管如何等重量边缘已订购，之后采用Kruskal算法的MK以上边缘添加步骤，对应于M上的顶点的米树将已合并成k树，与第j个树由对应于C（i）所述第j个成分的顶点的树木，加权重w的一个或多个边缘的结合的，对于每一个1 <= j的<= K。 具体地，该组中的每个所得树k的顶点是由产生了边缘在C（i）所述重瓦特边缘的特定排序不受影响。
证明：每边（u，v）的在C（ⅰ）对应于R（I）的重瓦特边缘可能出现在等重量的边缘的一些置换所有的重量-W的边缘中的第一，并且因此可以被选择通过克鲁斯卡尔算法未来。 加入它的效果将是在F（ⅰ）两个树连接在一起成一个在F（I + 1），并于从R丢弃一个或多个边缘（I + 1）。 在部件图形效果会合并u和v在C（ⅰ）成在C语言的单个顶点X（I + 1），删除u和v之间的所有其他平行边缘在C（I + 1），和改变第三顶点y和U或v IN C（I）之间的所有边缘到y和新的顶点x与在C（I + 1）的边缘。 如果的Kruskal下选择在C（i）一个部件的边缘，在其它部件的边缘不会受到影响，因此，如何对不同的组件的边缘中的排列是交错的没有效果。 因此，我们可以假设一个组件的所有边缘都首先看到的，然后另一个组件的所有边缘，依此类推，直到第k个分量。 假设第一组分具有s个点。 通过采用Kruskal算法添加的每个边缘减少了由1这个组件的顶点的数量，而不断开的组件。 边缘的在C（I + J）成分的存在指示中的R的重瓦特边缘的存在，连接在F（I + J）两个不同的树（I + J），所以采用Kruskal算法将继续选择，直到它变成在C语言的单个顶点的是缩水此组件边缘（I + S-1）。 无论哪个边缘在每一步选择，在F中的相应的树的顶点（I + S-1）将包括从S树F（I）的所有顶点的并集的。 这可以重复其余组件。 如果有跨在所有k个分量m个顶点，然后MK要求步骤，在每个部件收缩到一个顶点。
计数MSTS
定理：MSTS的数量是在对每个块限定i中的多重图C（I）跨越森林的数量的乘积。
证明：由于确立了在引理，可以通过对在C（i）所述边缘的一些置换运行的Kruskal产生每森林是相对于在F中的每个所得树组件的顶点集的第（i + MK）是相同的。 C（I）的S-顶点部件的每个生成树代表一组不同的S-1的边缘，可以由采用Kruskal算法来选择，以产生包含在F中的相应集合S树的不同底层MST（ⅰ） 。 甲生成森林是生成树，一个用于每个部件的组合，所以跨越森林的数量是跨越每个包含树的树的数目的乘积。 呼叫跨越森林在C（I）Q（I）的数量。 由于在随后的Kruskal块边缘加成步骤不关心每个组件的边缘结构，但只有大约是在每个组件中什么顶点，跨越所述块森林Q（I）的任何选择起始于步骤i不影响q（j）的所有森林q（I）*跨越森林为下一个块开始于步骤j> I的数目，和是不同的。
有几分用于计算图的生成树，如一个基于数量的复杂算法基尔霍夫定理 ， 通过imslavko给出 。 我不知道，如果一个会为重图工作。 但在任何情况下，由于我们只关心特定的情况下1,2和2个以上，我们可以走捷径。
如果我们只是要检测的图是否具有完全1 MST或大于1时，我们可以使用一个事实，即整数的产品，只有这样才能等于1是如果每个系数等于1：如果有块，即对C（I）超过1个生成树，立即停止并报告“超过1”。 如果我们到年底没有发生这种情况，汇报“1”。
如果我们要检测的图是否有确切2 MSTS，我们可以使用一个事实，即整数的乘积等于2，准确的因素1一定等于2和所有其余的必须是1。对于多图具有完全相同2生成树，它必须由林加上已经有他们之间的边两个顶点之间只有一个额外的（平行）边缘。 （含有的k周期对于k的任何多重图> = 3必须有至少K个生成树，通过删除k条边中的任意1形成。）
算法概述
执行的Kruskal如常，但每当一个新的块开始（通过添加具有比任何之前添加的边缘更高的权重的边缘），在添加前边缘，执行以下步骤：
- 创建一个空的多重图，C，使用邻接表表示。
- 向前扫描通过具有这种权重的所有其余边缘，并且对于每个边（u，v）中，添加（C（U），C（v））中，以C，其中C（V）为v的由联合发现代表节点/查找结构被用来检查连接。
- 通过这种多重图的每个组件执行DFS，使用标志的数组来记录已经被访问过的顶点。 此DFS的目的是检查周期和平行的边缘：
- 如果存在长度为3或更高的任何循环，该组件具有至少3个生成树，这意味着该算法可以在这一点终止。
- 如果任何边缘平行与多重性3个或更多出现时，所述算法可同样终止的时候了。
- 每双边两个顶点之间上线时间，增加全局计数器：如果计数器必须高于1，那么至少2 * 2 = 4 MSTS存在，所以该算法能够再次终止的时候了。 如果我们得到的克鲁斯卡算法结束时，计数器为1，则正好2个MSTS存在; 否则它必须是在0，在这种情况下，正好1 MST存在。
所有这些额外的操作采取边不相交块线性时间，因此他们将不会增加潜在的克鲁斯卡算法的过去澳时间复杂度（E日志V）。
Answer 2:
我知道算法来决定不同的生成树数：这个算法中使用基尔霍夫定理。 我记得大约求解最小的树木数量的问题，但它是指数的，如果我没有记错。 主要思想是在试探树和包括，排除方法使用边位掩码。
顺便说一句，如果边缘的所有的权重是不同的，那么只有一个MST。 希望能帮助到你。
文章来源: An algorithm to see if there are exactly two MSTs in a graph?
