3

假设连通图的边数已知并且每条边的权重不同，是否可以在线性时间内创建最小生成树？

为此，我们必须查看每个边缘；并且在此循环期间不能包含任何搜索，否则将导致至少 n log n 时间。如果不在循环中搜索，我不确定如何做到这一点。这意味着，不知何故，我们必须只查看每条边一次，并根据一些不涉及不断增长的数据结构的“静态”先前值来决定是否包含它。

所以..假设我们保留有问题的节点的端点，然后查看下一个节点，如果下一个节点与prev具有相同的顶点，则比较prev和当前节点的权重并保留较低的那个。如果当前节点的端点不等于 prev，那么它在不同的组件中.. 现在我被卡住了，因为我们无法创建哈希或数组来跟踪已经添加的组件节点，同时以线性方式查看每条边时间。

我想到的另一种方法是找到权重最小的边缘；由于边缘权重不同，因此该边缘将成为任何 MST 的一部分。然后..我被卡住了。因为我们不能在线性时间内对 n - 1 条边执行此操作。

有什么提示吗？

编辑

如果我们知道节点的数量、边的数量以及每个边的权重是不同的怎么办？比如说，有 n 个节点，n + 6 条边？

那么我们只需要找到并删除正确的 7 个边对吗？

4

4 回答 4

2

据我所知，没有办法通过知道图中有多少条边并且它们是不同的来更快地计算 MST。在最坏的情况下，您必须先查看图中的每条边，然后才能找到最小成本边（必须在 MST 中），这在最坏的情况下需要 Ω(m) 时间。因此，我声称任何MST 算法在最坏的情况下都必须花费 Ω(m) 时间。

但是，如果我们已经在最坏情况下进行 Ω(m) 工作，我们可以对任何 MST 算法执行以下预处理步骤：

  1. 扫描边缘并计算有多少。
  2. 为每个边权重添加一个 epsilon 值，以确保边是唯一的。

这也可以在时间 Ω(m) 内完成。因此，如果有一种方法可以在知道边数且边成本不同的情况下加速 MST 计算，我们只需对任何当前的 MST 算法执行此预处理步骤，以尝试获得更快的性能。由于据我所知，没有 MST 算法实际上出于性能原因尝试这样做，我怀疑没有（已知的）方法可以根据这些额外知识获得更快的 MST 算法。

希望这可以帮助！

于 2013-05-31T23:54:33.543 回答
2

有一种著名的最小生成树随机线性时间算法，其复杂性与边数成线性关系。请参阅 Karger、Klein 和 Tarjan 的“用于查找最小生成树的随机线性时间算法”。

论文中的关键结果是他们的“采样引理”——如果你独立地随机选择概率为 p 的边子集并找到该子图的最小生成树，那么只有 |V|/p 个边比连接其末端的树路径中的最差边缘要好。

正如 templatetypedef 所指出的，您无法击败线性时间。所有边缘权重都是不同的是简化分析的常见假设；如果有的话，它会使 MST 算法运行得慢一些。

于 2013-06-01T00:41:12.523 回答
1

已知许多边 (N) 的事实不会以任何方式影响复杂性。N 仍然是一个有限但无界的变量，每个图都有不同的 N。如果你在 N 上设置一个上限，比如 100 万，那么复杂度是 O(100 万对 100 万) = O(1)。

每条边都有不同的权重这一事实也不会影响程序，因为它没有说明图的结构。因此，关于当前案例的知识不会影响进一步的处理，因为我们无法预测下一步图的结构会是什么样子。

于 2013-05-31T23:58:39.170 回答
0

如果边数接近 n，就像在这种情况下n-6（编辑后），我们知道我们只需要删除 7 条边，因为每个生成树都只有n-1边。循环属性表明循环中最昂贵的边不属于任何最小生成树（假设所有边都是不同的），因此应该删除。

现在您可以简单地应用BFS或DFS来识别循环并移除最昂贵的边缘。所以，总的来说，我们需要运行 BFS 7 次。这需要7*n时间并且给我们一个时间复杂度O(n)。同样，这仅在边数接近节点数时才成立。

于 2018-09-28T07:03:29.790 回答