我有一个无向连通图，G。我希望能够找到一个算法，返回true，如果至少有2 MSTS。

I have an undirected connected graph G. I wish to find an algorithm that return true if there are at least 2 MSTs.

如果我想看看是否有确切2 MSTS？

What if I want to see if there are exactly 2 MSTs?

推荐答案

我们可以通过修改克鲁斯卡尔算法有效地检测这两种情况。如果有人能想到一个简单的方法来描述这一切，请让我知道！

We can detect both cases efficiently by modifying the Kruskal algorithm. If someone can think of a simpler way to describe all this, please let me know!

克鲁斯卡尔算法通过始终包括连接已建成至今森林的不同组件的下边缘最小构建一个MST。该算法是正确的，只要任何的这种最小的边缘被选中，即无论怎么边具有相等的权重是有序的。

The Kruskal algorithm builds an MST by always including the next-smallest edge that connects different components of the forest that has been built so far. The algorithm is correct whenever any such minimal edge is selected, i.e. regardless of how edges having equal weights are ordered.

此外，每个的MST可以通过选择某些特定的方式订购每一套相等重量的边缘，然后运行的Kruskal算法产生。要看到这一点，假设有一些MST无法产生这种方式。现在减去一些少量小量从本台MST每条边的权重（比任何一对不等边权之间的差更小）：这台MST是现在的独特台MST，因此采用Kruskal必须产生这台MST与新的边权运行时。但是，因为我们只至多ε，当边缘被按重量排序调整边缘通过，该组具有重量w_i所有边的 - 小量必须出现（在一些顺序）立即preceding该组具有重量w_i边缘（在一些命令），在两组之间没有其他的边缘。但是，这是一个有效的顺序可能为原始的，未经修改的边缘，而克鲁斯卡尔算法只在乎的边缘，而不是他们的特殊权重的排序，因此克鲁斯卡尔算法必须已经产生了MST从排序中。这与我们的假设，因此它必须是克鲁斯卡尔算法可以产生每一个MST。

Furthermore, every MST can be produced by choosing some particular way to order every set of equal-weight edges, and then running the Kruskal algorithm. To see this, suppose there was some MST that could not be produced this way. Now subtract some small amount epsilon (smaller than the difference between any pair of unequal edge weights) from the weight of each edge in this MST: this MST is now the unique MST, so Kruskal must produce this MST when run with the new edge weights. But because we only adjusted edges by at most epsilon, when the edges are sorted by weight, the set of all edges having weight w_i - epsilon must appear (in some order) immediately preceding the set of edges having weight w_i (in some order), with no other edges in between the two groups. But this is a valid possible ordering for the original, unmodified edges, and the Kruskal algorithm only cares about the ordering of edges and not their particular weights, so the Kruskal algorithm must have produced the MST from that ordering as well. This contradicts our assumption, so it must be that the Kruskal algorithm can produce every MST.

呼叫通过采用Kruskal算法构建的森林I> = 0边沿加成后步骤F（i）中，并且边缘其余要考虑，且不会因创建一个循环的R（i）中。 （当边缘在步骤加入I，我们形成R（i）在开始有R（ⅰ-1的副本），并删除刚刚加入边缘，并且加入了同一对组件的所有其它边缘。虽然采用Kruskal算法实际上消除了这些其它边缘懒惰，所定义的R（i）本方式简化证明算法性能。）我们将打散的Kruskal算法成一系列的块的，其每一个由一个序列的边缘加法其中相同重量的边缘被加入。呼叫我的块定义如果任一I = 0，或R（I）的最小重量边缘大于任何优势，在步骤1中添加的..我。

Call the forest built by the Kruskal algorithm after i >= 0 edge-addition steps F(i), and the edges remaining to be considered and which would not create a cycle R(i). (When an edge is added in step i, we form R(i) by starting with a copy of R(i-1) and deleting the just-added edge and all other edges that joined the same pair of components. Although the Kruskal algorithm actually eliminates these other edges "lazily", defining R(i) this way simplifies proving algorithm properties.) We will break up the Kruskal algorithm into a series of blocks, each of which consists of a sequence of edge additions in which edges of the same weight are added. Call i block-defining if either i = 0, or the minimum-weight edge in R(i) is larger than any edge added in steps 1 .. i.

假设一些块限定数目i之后> = 0的边缘加成步骤中的Kruskal算法已被执行时，在R（i）该最小边（即不会造成循环下一个最小的边缘）有重量瓦特采用Kruskal算法将进行到连接在一起别的做任何事情之前具有以某种方式在它们之间的重瓦特边缘所有树木，以及即使选择这些相等权重的边缘不同的边缘次序可能会影响到树木的生产，它可以在不影响中的组顶点在的每棵树。使这更precise：

Suppose that after some block-defining number i >= 0 of edge-addition steps of the Kruskal algorithm have been performed, the smallest edge in R(i) (i.e. the next-smallest edge that would not create a cycle) has weight w. The Kruskal algorithm will proceed to join together all trees having a weight-w edge between them in some way before doing anything else, and even though choosing a different edge ordering for these equal-weight edges can affect what trees are produced, it cannot affect the set of vertices in each tree. Making this more precise:

定义一个新的，未加权重图包括一个顶点为在森林F（i）每一组件（树）的（即，曲线图，其可以具有单个顶点对之间的多个边）C（i）中。为任何顶点v在C（i）中，调用吨（ⅴ）中的树F（i）该对应于诉创建C中的边缘的两个顶点u和v之间每当重瓦特边缘R中存在（ⅰ）在吨（u）的一些顶点和在吨一些顶点之间（体积）。调用C（I）中的组件图我几步后的。

Define a new, unweighted multigraph (that is, a graph that can have multiple edges between a single pair of vertices) C(i) consisting of a vertex for each component (tree) in the forest F(i). For any vertex v in C(i), call t(v) the tree in F(i) that corresponds to v. Create an edge in C between two vertices u and v whenever a weight-w edge exists in R(i) between some vertex in t(u) and some vertex in t(v). Call C(i) the component graph after i steps.

引理：假设，对于一些块定义数字I，C（我）有k个成分含有至少1个边缘（即组件不是单一的顶点），以及这些组件之间有米总> = 2k的顶点。称这组顶点M的那么不管如何同等重量的边缘已订购，后MK以上边缘添加步骤克鲁斯卡尔算法，对应于M中的顶点并购的树木将被合并为k的树，用第j个树由对应于C（i）所述第j个成分的顶点的树木，加权重w的一个或多个边缘的并集，对于每个1所述; = J＆其中; = K。尤其是，该组中的每个所得树k的顶点的不受重瓦特边缘即引起了边缘在C中（i）的特定排序

Lemma: Suppose that for some block-defining number i, C(i) has k components containing at least 1 edge (i.e. components that are not single vertices), and among these components there are m >= 2k vertices in total. Call this set of vertices M. Then regardless of how equal-weight edges have been ordered, after m-k more edge-addition steps of the Kruskal algorithm, the m trees corresponding to the vertices in M will have been merged into k trees, with the jth tree consisting of the union of the trees corresponding to the vertices of the jth component of C(i), plus one or more edges of weight w, for each 1 <= j <= k. In particular, the set of vertices in each of the k resulting trees is unaffected by the particular ordering of the weight-w edges that gave rise to the edges in C(i).

证明：每边（u，v）的在C（I）对应于R（I）的重量-W的边缘，可能首先出现在一些排列所有的重量-W的边缘之间等于重量边缘，因此，可以由下一次采用Kruskal算法选择。将其添加的效果将是在F（ⅰ）两个树合流成一个在F中第（i + 1），并以自R丢弃一个或多个边缘第（i + 1）。上组件图中的效果将合并u和v在C中（ⅰ）成一个单一的顶点中的x C（i + 1的）中，删除在C中第（i + 1），并改变u和v之间的所有其它平行的边缘第三顶点y和任u或v在C中（ⅰ）之间的所有边到y和新顶点x之间C中的边缘第（i + 1）。如果在C（i）一种组分的边缘选择下一个的Kruskal，在其它部件的边缘不受影响，所以对于不同的组件的边缘如何被交织在排列没有任何效果。因此，我们可以假设，对于一个组件所有边缘首先看到的，那么所有的另一组件的边缘，依此类推，直到第k个分量。假设，第一组分有小号顶点。由克鲁斯卡尔算法添加的每个边缘降低此部分由1个顶点的数量没有断开的组件。在C中的部件边缘的presence（I + J）表示R中的权重-W边缘的presence（I + J），用于连接两个不同的树F（I + J），所以采用Kruskal算法将继续选择边缘即收缩此组件，直到它变成在C中一个顶点（ⅰ+ S-1）。其中无论边缘被选择在每一步，在F中的相应的树中的顶点（ⅰ+ S-1）将包括从树丛在F（i）所有顶点的联盟。这可以重复对其余组件。如果有跨K Components产品在所有的M顶点，然后MK是必要的步骤，以每个部件收缩到一个顶点。

Proof: Every edge (u, v) in C(i) corresponds to a weight-w edge in R(i) that could appear first among all weight-w edges in some permutation of equal-weight edges, and therefore could be chosen next by the Kruskal algorithm. The effect of adding it will be to join together two trees in F(i) into one in F(i+1), and to discard one or more edges from R(i+1). The effect on the component graph will be to merge u and v in C(i) into a single vertex x in C(i+1), delete all other parallel edges between u and v in C(i+1), and change all edges between a third vertex y and either u or v in C(i) into an edge between y and the new vertex x in C(i+1). If an edge in one component of C(i) is chosen next by Kruskal, edges in other components are not affected, so how the edges for different components are interleaved in the permutation has no effect. Therefore we can suppose that all edges for one component are seen first, then all edges for another component, and so on until the kth component. Suppose the first component has s vertices. Each edge added by the Kruskal algorithm reduces the number of vertices of this component by 1 without disconnecting the component. The presence of an edge in the component in C(i+j) indicates the presence of a weight-w edge in R(i+j) that connects two distinct trees in F(i+j), so the Kruskal algorithm will continue to choose edges that shrink this component until it becomes a single vertex in C(i+s-1). Regardless of which edges are chosen at each step, the vertices in the corresponding tree in F(i+s-1) will consist of the union of all vertices from the s trees in F(i). This can be repeated for the remaining components. If there are m vertices across k components in all, then m-k steps are required to shrink each component to a single vertex.

定理： MSTS的数量是跨越森林的多重图C（I）的数的乘积每个块定义I

Theorem: The number of MSTs is the product of the number of spanning forests in the multigraph C(i) for each block-defining i.

证明：如既定在引理，可以通过对在C中（i）所述边缘的一些置换运行秩来制备每森林相同相对于顶点的集合中的每个所得树组件在F（1 + MK）。 C（ⅰ）的重新$ P $的s顶点组件的每个生成树psents一组的s-1的边缘，可以通过采用Kruskal算法来选择，以产生包含相应的一组第树木中一个独特的底层台MST不同F（i）中。甲生成森林是生成树，一个用于每个组件的组合，以便跨越森林的数量是生成树包含的每个树的数量的乘积。呼叫跨越森林在C（ⅰ）Q（I）的数目。因为在随后的Kruskal块边缘加成步骤不关心的每个组件的边缘结构，但仅关于什么顶点中的每个组件时，q（ⅰ）跨越森林对块的任何选择起始于步骤i不影响跨越森林下一个块起始步骤j数>我和所有的Q（I）* Q（J）森林是不同的。

Proof: As established in the lemma, every forest that can be produced by running Kruskal on some permutation of the edges in C(i) is identical with respect to the sets of vertices in each resulting tree component in F(i+m-k). Each spanning tree of an s-vertex component of C(i) represents a distinct set of s-1 edges that can be selected by the Kruskal algorithm to produce a distinct underlying MST that contains the corresponding set of s trees in F(i). A spanning forest is a combination of spanning trees, one for each component, so the number of spanning forests is the product of the number of spanning trees for each contained tree. Call the number of spanning forests in C(i) q(i). Since edge-addition steps in subsequent Kruskal blocks do not care about the edge structure of each component but only about what vertices are in each component, any choice of the q(i) spanning forests for the block starting at step i does not affect the number of spanning forests for the next block starting at step j > i, and all q(i) * q(j) forests are distinct.

有比较复杂的算法，用于计算图的生成树，如一个基于基尔霍夫定理，由imslavko 给出。我不知道这人会工作的多重图。但在任何情况下，由于我们只关心特定案件1，2和2个以上，我们可以采取的捷径。

There are somewhat complicated algorithms for calculating the number of spanning trees of a graph, such as the one based on Kirchhoff's theorem, given by imslavko. I'm not sure if that one will work for multigraphs. But in any case, since we only care about the particular cases 1, 2 and more than 2, we can take shortcuts.

如果我们只是想检测图中是否有确切1 MST或大于1时，我们可以用这样一个事实：整数的产品，只有这样才能等于1是，如果每一个因子等于1：即如果有块有​​1个多跨越的C（I）树，立即停止并报告超过1。如果我们到最后没有这种情况发生，报告中1。

If we only want to detect whether the graph has exactly 1 MST or more than 1, we can use the fact that the only way for a product of integers to be equal to 1 is if every factor is equal to 1: i.e. if any block has more than 1 spanning tree for C(i), immediately stop and report "More than 1". If we get to the end without this happening, report "1".

如果我们要检测的图是否正好有2 MSTS，我们可以使用这一事实为整数的乘积为等于2，完全1的因素必须等于2和所有其余必须是1。对于多重图有确切2生成树，它必须由森林和两个已经有他们之间的边缘顶点之间只有一个额外的（水货）的边缘。 （含K-周期对于k的任何重图> = 3必须有至少k生成树，删去任何1 k条边的形成。）

If we want to detect whether the graph has exactly 2 MSTs, we can use the fact that for a product of integers to be equal to 2, exactly 1 of the factors must be equal to 2 and all the rest must be 1. For a multigraph to have exactly 2 spanning trees, it must consist of a forest plus exactly one additional (parallel) edge between two vertices that already have an edge between them. (Any multigraph containing a k-cycle for k >= 3 must have at least k spanning trees, formed by deleting any 1 of the k edges.)

执行秩像往常一样，但每当开始一个新块（添加有重量比任何previously添加边缘高出一个边缘），加入沿之前，请执行以下步骤：

Perform Kruskal as usual, but whenever a new block begins (indicated by an edge being added that has higher weight than any previously added edge), before adding the edge, perform the following steps:

创建一个空的多重图，C，使用邻接表重新presentation。 在向前扫描有这个重量所有剩余的边缘，并为每个边（u，v）的，加（C（U），C（V））为C，其中C（V）是重presentative诉节点被联盟发现/查找结构被用来检查连接。 通过这个多重图的每个组件执行DFS，使用标志数组，记录哪些顶点已被访问。本的DFS的目的是检查周期和平行的边缘： 如果存在长度为3或更高的任何循环，该组件具有至少3个生成树，这意味着该算法可以终止在这一点上。 如果任何并行边出现了多重性3个或更多，算法同样可以终止的时候了。 在每次双力被认为是两个顶点之间，增加一个全局计数器：如果计数器变为大于1，则至少有2 * 2 = 4 MSTS存在，所以该算法可以再次终止的时候了。如果我们得到采用Kruskal算法的端部和对置为1，然后准确2 MSTS存在;否则它必须是在0，在这种情况下，正好1台MST存在。 Create an empty multigraph, C, using an adjacency-list representation. Scan forward through all remaining edges having this weight, and for each edge (u, v), add (c(u), c(v)) to C, where c(v) is the representative node of v found by the union/find structure being used to check for connectivity. Perform a DFS through each component of this multigraph, using an array of flags to record which vertices have already been visited. The purpose of this DFS is to check for cycles and parallel edges: If there any cycles of length 3 or higher, the component has at least 3 spanning trees, meaning the algorithm can terminate at this point. If any parallel edge appears with multiplicity 3 or more, the algorithm can likewise terminate right away. Every time a double-edge is seen between two vertices, increment a global counter: if this counter goes above 1, then at least 2*2 = 4 MSTs exist, so the algorithm can again terminate right away. If we get to the end of the Kruskal algorithm and the counter is at 1, then exactly 2 MSTs exist; otherwise it must be at 0, in which case exactly 1 MST exists.

所有这些额外的操作采取边不相交块的线性时间，因此他们将不会增加潜在的克鲁斯卡尔算法的时间复杂度过去的O（ē日志V）。

All of these additional operations take linear time on disjoint blocks of edges, so they won't increase the time complexity of the underlying Kruskal algorithm past O(E log V).