无向连通图 - 查找属于MST的具有特定权重的边

Question

问题：

给定一个无向连通图 G，其边上有权重，具体权重为 X，
编写算法，查找 G 中属于 G 的某个 MST 且权重为 X 的所有边

显然你可以以线性时间复杂度 O(V+E) 来完成。

• 我这里的方法是对边进行排序（升序），然后删除权重X及以上的所有边，在图上运行DFS，然后检查权重X的每条边是否在添加边时，图是连通的，如果那么权重 X 的这条边确实属于 MSB

但我认为我在算法中遗漏了一些东西（例如，如果我有一个所有边的权重为 X 的循环怎么办），并且关于时间复杂度排序将采取 (E * Log(E))，DFS 将采取O(V+E) (V+E) 比 (Elog(E)) 更好还是更差？

此外，我需要检查我“检查”图形是否仍然连接的每条边（那么我如何在 O(V+E) 中做到这一点？再次运行 dfs 会花费更多时间，因为我需要运行dfs - 作为权重 X) 的边数？

Answer 1

您可以通过采用 Kruskal 算法：

在线性时间内解决此问题

1. 使G的子图仅包含权重小于X的边；

2. 找到该子图的连通分量，并用与其连通分量对应的数字标记每个顶点；

3. 找到连接具有不同标签的顶点的所有权重为 X 的边。其中每一个都至少处于一个 MST 中。