设g=（v，e）为加权连通无向图。设t1和t2是两个不同的mst。假设我们可以写出e=（a1 u b u a2），这样：
B是T1和T2边缘的交点，并且
A1=T1-B
A2=T2-B
假设g中的每个mst都包含b的所有边，那么找到一个算法来确定是否有一个mst在a1中至少包含一条边，在a2中至少包含一条边。
编辑：我把这里的部分掉了。我认为它弊大于利。
最佳答案
您应该将您的边缘排序为红色边缘比蓝色边缘更适合选择。然后，您可以使用与Prim算法相同的任何mst算法：
如果一个图是空的，那么我们立即完成因此，我们假设
否则。算法从一棵树开始，该树由一个
顶点，并一次连续增加一条边的大小，直到
它跨越所有顶点。输入：非空连通加权图
顶点为v，边为e（权重可以为负）。初始化：
vnew={x}，其中x是v，enew的任意节点（起点）
={}重复直到vnew=v：选择一个最小权重的边{u，v}，使u在vnew中而v不在（如果有多个边具有
相同的重量，任何一个都可以选择）将v添加到Vnew，然后{u，v}
enew输出：vnew和enew描述最小生成树