图中的边属性
图中的边属性
提问于 2019-01-03 21:29:12
给定一个G(V,E)加权(在边上)图，我需要找出属于每个MST的边的数量，以及属于至少一个但不是所有的边的数量，以及属于none的边的数量。
该图以以下形式(示例)作为输入：
3 3
1 2 1 ->edge(1,2),weight=1
1 3 1
2 3 1First 3是节点的数量，second 3是edges.The的数量，后面三行是边，其中第一个数字是它们的起点，第二个是它们结束的地方，第三个是值。
我曾经想过运行一次Kruskal来查找MST，然后对属于G的每条边进行签入(线性？)如果它可以在不改变MST整体权重的情况下替换MST中的一条边，则需要时间。如果它不能，它就不属于none。如果可以，它属于一个，但不是全部。我还可以标记第一个MST中的边(可能用第二个值1或0)，最后检查有多少边无法替换。这些是属于每个可能的MST的。这个算法可能是O(V^2)的，我不太确定如何用C++编写它。我的问题是，我们能以某种方式降低它的复杂性吗？如果我向MST添加一个边，我如何检查(并在C++中实现)形成的循环是否包含一个权重较小的边？
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-01-04 01:51:21
我认为重要的是要注意，每个MST都有相同的边权重集。用这些知识武装起来：
- 使用某种算法构建一个MST。
- 为MST中的每条边创建将MST分成两部分的割线。
- 检查cut
- 中是否存在具有相同权重的其他边。如果存在，则这些边都属于某个MST，
<>H19如果没有，则该边属于唯一的MST
- 所有其他边不属于任何MST。
我们可以将其转换为以下算法。使用Prim的算法，只是在每一步上不仅要添加具有最小权重的边，而且要标记具有该权重的所有边，如果有多个这样的边，则标记为II类型的边，如果只有一条这样的边，则标记为I类型的边。所有未标记的边都属于III类型。
I -属于all，II -属于至少一个，III -不属于任何一个。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54023252
复制相关文章
相似问题