给定多重图的邻接表 G = (V, E)，需要找到一个 O(V + E) 算法来计算等效无向图的邻接表。
到目前为止，我已经想到了一个大小为 |V| 的数组。以便在 adj[u] 中标记至少遇到一次的顶点，从而防止重复。数组在遍历每个 adj[u] 之前被重置。但是，我想知道是否存在不使用额外空间的更好算法。请建议。
问问题
1759 次
4 回答
1
如果要达到O(V+E)时间复杂度，没有更好的算法，因为这基本上是元素区别问题的变体，可以通过排序解决O(nlogn)，或者在 中使用O(n)额外的空间O(n)。
因此，要实现 O(V+E) 时间，您的算法是最优的（就大 O 表示法而言）
于 2013-08-12T13:50:37.743 回答
1
作为参考，应该注意的是，从技术上讲，每次重置数组时都会使用 O(V) 时间。数组创建在技术上不是免费的，因为它是使用随机指针创建的，不能保证这些值是什么。因此，它需要一次通过才能将它们实际初始化为 0 或 null。因此，您提出的算法的运行时间变为 O(V^2)。
我知道这个问题现在已经解决了，但是应该注意这个事实。
于 2017-03-24T20:58:05.903 回答
0
您可以使用无序集数据结构将 O(n) 额外空间改进为 O（最大邻居数），只需检查没有邻居被两次添加到邻接列表中。
于 2013-08-13T12:00:26.547 回答
0
遇到了同样的问题。
经过思考，我想为您的解决方案建议一个快速的小修复。正如@sunnytheit 提到的 - 在两个不同的邻接列表之间的每两次迭代之间，您必须重置指示数组。这个动作确实会带你 $\Theta(|V|)$ （总起来就是多项式运行时复杂度）。要修复它，您可以将堆栈与数组并行使用。
一旦你到达当前 adj-list 中的一个顶点，你首先检查它是否位于数组中，如果是，你继续下一个邻居。如果没有，则将其压入堆栈并更新数组中的指示值。
当你在当前的 adj-list 上完成运行时，你想弹出你在那个 adj-list 上遇到的元素，并且对于每个值你想重置数组中的相应值。
总的来说，它总计两次通过图形的边缘。因此，最终运行时复杂度将是 $\Theta(|V|+|E|)$ 所要求的。
备注：您可以通过使用某种 BST 而不是数组来节省额外的空间 - 但您必须分析它对运行时复杂性的影响。
于 2017-05-29T09:03:27.470 回答