检查边缘是否包含在线性时间中的某些MST中（非明显值） [英] Check if edge is included in SOME MST in linear time (non-distinct values)

问题描述

我正在研究一种算法，以检查所有可能的mst之一中是否包括给定的边。

I am working on an algorithm to check if a given edge is included in one of all possible mst's.

对于此问题，我们正在考虑使用非唯一值并且我们的边缘e连接顶点A& B。

For this question, we are considering non-distinct values and our edge e connects vertices A & B.

到目前为止，我有：如果可以从A到B的路径由权重小于或等于边e的权重的边组成， -我们可以说边缘e不是任何MST的一部分。

So far, I have: If a path can be made from A to B consisting of edges with weights less than or equal to the weight of our edge e--we can say that edge e is not a part of any MST.

我在这里是否缺少任何内容/关于更好算法的想法？

Am I missing anything here/ ideas on a better algorithm?

编辑：

关于涉及循环属性的解决方案有何想法-因此，我们认为所有边的权重小于我们的边考虑。如果我们可以从具有这些边缘的A-> B建立路径，可以说它不属于任何MST？

What are thoughts on a solution involving the cycle property-- So, we consider all edges with weight less than the edge we are considering. If we can make a path from A->B with those edges, we can say that it is not part of any MST?

推荐答案

我们将使用 MST周期属性来解决此问题，它表示对于任何周期图中的C，如果C的边e的权重大于C的所有其他边的权重，则该边不能属于MST。

We will solve this using MST cycle property, which says that, "For any cycle C in the graph, if the weight of an edge e of C is larger than the weights of all other edges of C, then this edge cannot belong to an MST."

现在，运行以下 O（E + V）算法以测试连接顶点u和v的边E是否会成为某些MST的一部分。

Now, run the following O(E+V) algorithm to test if the edge E connecting vertices u and v will be a part of some MST or not.

步骤1

从一个端点（u或v）运行dfs ）仅考虑重量小于E的那些边缘。

Run dfs from one of the end-points(either u or v) of the edge E considering only those edges that have weight less than that of E.

步骤2

情况1
如果在此dfs的末尾，顶点u和v连接在一起，则边E不能成为某些MST的一部分。这是因为在这种情况下，图形中肯定存在一个循环，其边缘E具有最大权重，并且它不能成为MST的一部分（根据循环属性）。

Case 1 If at the end of this dfs, the vertices u and v get connected, then edge E cannot be a part of some MST. This is because in this case there definitely exists a cycle in the graph with the edge E having the maximum weight and it cannot be a part of the MST(from the cycle property).

情况2
但是，如果dfs的末尾u和v保持断开状态，则边缘E必须是在这种情况下，某些MST始终不是它所属于的所有循环中的最大重量边。

Case 2 But if at the end of the dfs u and v stay disconnected, then edge E must be the part of some MST as in this case E is always not the maximum weight edge in all the cycles that it is a part of.

这篇关于检查边缘是否包含在线性时间中的某些MST中（非明显值）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！