图中的边属性
Edge properties in a graph
给定一个 G(V,E) 加权（边）图，我需要找到属于每个 MST 的边数以及属于至少一个但不是全部和属于 none.
的那些
图形以以下形式作为输入给出（示例）：
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1
第一个3是节点的数量，第二个3是edges.The的数量下面三行是边，第一个数字是它们开始的地方，第二个是它们的地方结束和第三个是价值。
我曾经考虑过 运行 Kruskal 来找到一个 MST，然后对于属于 G 的每条边检查（线性？）时间如果它可以替换这个 MST 中的边而不用改变它的整体重量。如果不能，它属于 none。如果可以的话，它属于一个但不是全部。我还可以在第一个 MST 中标记边缘（可能使用第二个值 1 或 0），最后检查其中有多少不能被替换。这些是属于每个可能的 MST 的。
这个算法可能是 O(V^2)，我不太确定如何用 C++ 编写它。我的问题是，我们能否以某种方式降低它的复杂性？
如果我向 MST 添加边，我如何检查（并在 C++ 中实现）形成的循环是否包含权重较小的边？
我认为重要的是要注意每个 MST 都具有相同的边权重集。有了这些知识：
- 使用某种算法构建 MST。
- 为 MST 中的每条边创建将 MST 分成两部分的切割。
- 检查切割中是否有其他具有相同权重的边
- 如果有，那么每条边都属于某个MST，
- 如果没有，则这条边属于唯一的MST。
- 所有其他边不属于任何 MST。
我们可以将其转化为如下算法。使用 Prim 算法，仅在每一步不仅添加具有最小权重的边，而且将具有该权重的所有边标记为 II 类型的边（如果有多个这样的边或 [=11 类型） =] 如果只有一个这样的边。所有未标记的边都是 III.
类型
I - 属于所有，II - 至少属于一个，III - 不属于任何一个。
给定一个 G(V,E) 加权（边）图，我需要找到属于每个 MST 的边数以及属于至少一个但不是全部和属于 none.
图形以以下形式作为输入给出（示例）：
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1
第一个3是节点的数量，第二个3是edges.The的数量下面三行是边，第一个数字是它们开始的地方，第二个是它们的地方结束和第三个是价值。
我曾经考虑过 运行 Kruskal 来找到一个 MST，然后对于属于 G 的每条边检查（线性？）时间如果它可以替换这个 MST 中的边而不用改变它的整体重量。如果不能，它属于 none。如果可以的话，它属于一个但不是全部。我还可以在第一个 MST 中标记边缘（可能使用第二个值 1 或 0），最后检查其中有多少不能被替换。这些是属于每个可能的 MST 的。
这个算法可能是 O(V^2)，我不太确定如何用 C++ 编写它。我的问题是，我们能否以某种方式降低它的复杂性？
如果我向 MST 添加边，我如何检查（并在 C++ 中实现）形成的循环是否包含权重较小的边？
我认为重要的是要注意每个 MST 都具有相同的边权重集。有了这些知识：
- 使用某种算法构建 MST。
- 为 MST 中的每条边创建将 MST 分成两部分的切割。
- 检查切割中是否有其他具有相同权重的边
- 如果有，那么每条边都属于某个MST，
- 如果没有，则这条边属于唯一的MST。
- 所有其他边不属于任何 MST。
我们可以将其转化为如下算法。使用 Prim 算法，仅在每一步不仅添加具有最小权重的边，而且将具有该权重的所有边标记为 II 类型的边（如果有多个这样的边或 [=11 类型） =] 如果只有一个这样的边。所有未标记的边都是 III.
I - 属于所有，II - 至少属于一个，III - 不属于任何一个。