图中的边属性

Question

给定一个加权有向图 G(V,E)，需要找出每个最小生成树中属于的边数以及属于至少一个但不是全部最小生成树的边的数量以及不属于任何最小生成树的边的数量。

输入的图以以下形式给出(示例)：

3 3

1 2 1 ->edge(1,2),weight=1

1 3 1

2 3 1

第一个3是节点数，第二个3是边数。接下来的三行是边，第一个数字代表起点，第二个数字代表终点，第三个数字代表权值。

我考虑运行Kruskal算法一次以找到最小生成树(MST)，然后对于每条属于G的边，在(linear?)时间内检查它是否可以替换掉MST中的一条边而不改变总权重。如果不能，则它不属于任何MST；如果可以，则它属于其中一个但不是所有MST。我还可以标记第一个MST中的边（也许用第二个值1或0），最后检查有多少边无法替换。这些边属于所有可能的MST。 这个算法的时间复杂度可能是O(V^2)，我不太确定如何在C++中编写它。我的问题是，我们能否以某种方式降低其复杂度？ 如果我将边添加到MST中，如何检查（并在C++中实现）形成的环是否包含权值更小的边？

- Epitheoritis 32

---

你确定你指的是边的数量而不是 E 的子集吗？如果是这样，那么生成树中的边数与实际边集无关（即为 |V|-1），详见此处。 - Codor

是的，对于我所举的例子，输出应为：0（包含在每个最小生成树中的边数），0（不包含在任何一个最小生成树中的边数），3（至少属于一些但不是全部最小生成树的边数）。 - Epitheoritis 32

我已经更新了我的答案，并附上了一个实现的描述。你可以自己实现Prim算法，也可以在互联网上找到一个实现。 - Yola

Answer 1

我认为需要注意的是每个最小生成树都有相同的边权集合。有了这个知识：

1. 使用某种算法构建最小生成树。
2. 对于最小生成树中的每条边，创建一个切割将最小生成树分成两部分。
3. 检查切割中是否存在其他具有相同权重的边
   • 如果存在，则每条这样的边都属于某个最小生成树，
   • 如果不存在，则此边属于唯一的最小生成树。
4. 所有其他边都不属于任何最小生成树。

---

我们可以将其转化为以下算法。使用Prim算法，但在每个步骤中，不仅添加权重最小的边，而是将所有具有此权重的边标记为类型I（如果只有一条这样的边）或类型II（如果有多条这样的边）。所有未标记的边都属于类型III。 I - 属于所有，II - 至少属于一个，III - 不属于任何一个。

- Yola