给定一个 G(V,E) 加权(边)图，我需要找到属于每个 MST 的边的数量以及属于至少一个但不是全部的边的数量以及属于每个 MST 的边的数量不属于任何人。
图形以以下形式作为输入给出(示例):
3 3
1 2 1
1 3 1
2 3 2
前3是节点数，后3是边数，后面三行是边，第一个数字是开始的地方，第二个是结束的地方，第三个是值。
我考虑过运行 kruskal 一次来找到一个 MST，然后对于属于 G 的每条边检查(线性？)时间如果它可以替换这个 MST 中的边而不改变它的整体权重。如果它可以'它不属于任何一个。如果它可以属于一个但不属于全部。我也可以在第一个 MST 中标记边缘(可能有第二个值 1 或 0)，最后检查其中有多少不能被替换.这些是属于每个可能的 MST 的。这个算法可能是 O(V^2)，我不太确定如何用 C++ 编写它。我的问题是，我们能以某种方式降低它的复杂性吗？如果我向 MST 添加一条边，我如何检查(并在 C++ 中实现)形成的循环是否包含权重较小的边？
最佳答案
您可以通过向 Kruskal 算法添加一些额外的工作来做到这一点。
在 Kruskal 算法中，具有相同权重的边可以有任何顺序，实际检查它们的顺序决定了您从所有可能的 MST 中得到哪个 MST。对于每个 MST，将生成该树的边具有排序一致的顺序。
无论使用何种排序一致顺序，联合查找结构的状态在权重之间都是相同的。
如果特定权重只有 一个 边，那么如果 Kruskal 算法选择它，则它在每个 MST 中，因为它会以任何排序一致的边顺序被选择，否则它是没有 MST。
如果有多条具有相同权重的边，并且 Kruskal 算法将至少选择其中一条，那么您可以在该点暂停 Kruskal 算法并制作一个新的(小)图，其中仅包含连接不同集合的那些边，使用它们作为顶点连接的集合。
所有这些边都至少在一个 MST 中，因为 Kruskal 可能会先选择它们。新图中任何作为桥的边都在每个 MST 中，因为无论如何 Kruskal 都会选择它们。请参阅:https://en.wikipedia.org/wiki/Bridge_(graph_theory)
因此，修改克鲁斯卡尔算法如下:
- 当 Kruskal 会选择一条边时，在进行并集之前，收集并处理所有具有相同权重的非冗余边。
- 使用 find() 集将这些边连接为顶点，用这些边制作一个小图
- 使用 Tarjan 算法或等效算法(参见链接)找到图中的所有桥梁。这些边缘在所有 MST 中。
- 小图中的剩余边在一些(但不是全部)MST 中。
- 对小图中的边执行所有并集，然后移动到下一个权重。
由于寻桥可以在线性时间内完成，并且每条边至多在一个小图中，整个算法仍然是O(|V| + |E| log |E|)。
关于algorithm - 图中 MST 边所必需的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/54026545/