algorithm - 判断是否存在包含 2 个不同边集的某些边的 MST

Question

设 G = (V, E) 是一个加权的、连通的和无向的图。令 T1 和 T2 为 2 个不同的 MST。假设我们可以这样写 E = (A1 U B U A2) :
B是T1和T2边的交点，
A1 = T1 - B
A2 = T2 - B

假设G中的每一个MST T都包含B的所有边，找到一种算法来决定是否存在一个MST T至少包含A1中的一条边和A2中的至少一条边。

编辑:我已经删除了这里的部分。我认为它弊大于利。

Answer 1

您应该对边缘进行排序，使红色边缘优于蓝色边缘以进行选择。然后您可以使用与 Prim 相同的任何 MST 算法。的算法:

If a graph is empty then we are done immediately. Thus, we assume otherwise. The algorithm starts with a tree consisting of a single vertex, and continuously increases its size one edge at a time, until it spans all vertices. Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative). Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {} Repeat until Vnew = V: Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, any of them may be picked) Add v to Vnew, and {u, v} to Enew Output: Vnew and Enew describe a minimal spanning tree