我们得到了多重图的邻接表 G = (V, E) 并且需要找到 O(V + E) 算法来计算等效无向图的邻接表。
到目前为止，我想到了一个大小为 |V| 的数组以便标记在 adj[u] 中至少遇到过一次的顶点，从而防止重复。在遍历每个 adj[u] 之前重置数组。但是，我想知道是否存在不使用额外空间的更好算法。请提出建议。
最佳答案
如果你想达到O(V+E)的时间复杂度，没有更好的算法，因为这基本上是element distinctness problem的变体。 ，这可以通过在 O(nlogn) 中排序来解决，或者通过在 O(n) 中使用 O(n) 额外空间来解决。
因此，为了实现 O(V+E) 时间，您的算法是最优的(根据大 O 表示法)
关于将多图的邻接表转换为等效无向图的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18187984/