给定一个多重图的邻接表，计算等价（简单）无向图的邻接表，时间复杂度为O（|V|+|E|）。

Question

3

我们得到了一个多重图G =（V，E）的邻接表，并需要找到一种O（V + E）算法来计算等效（简单的）无向图的邻接表。

我在另一篇文章中找到了以下解决方案（它是问题部分，因此我重新发布）：“[H]拥有一个大小为|V|的数组，以标记至少在adj [u]中被遇到一次的顶点，从而防止重复。在遍历每个adj [u]之前重置数组。”

请原谅我的无知，但我不确定这是O（| V | + | E |）的方法。重置长度为| V |的数组| V |次的成本是多少？

谢谢。

- tarski

取决于你认为什么是重置。可以是分配新内存并删除旧内存，用0覆盖每个值，或者仅忽略旧值并从0开始写入。引文缺乏上下文来判断这一点。而运行时复杂度的主要问题在于它高度依赖于被测量的内容（通常是最昂贵的操作，但这里非常模糊）。 - user4668606

嗨@Paul。你能想到任何“重置”的解释，可以满足复杂性要求吗？我认为我们不能忽略旧值... - tarski

1

如果您保留了已设置的顶点列表，则只需重置这些数组位置，因此取消设置的成本不会超过设置的成本，并且您可以将它们视为设置成本的常数因子。另一种方法是通过将其设置为整数值来设置数组中的位置，并在每次遍历时递增该整数值，将设置为小于当前值的任何值的位置视为未设置。 - mcdowella

1

@tarski，时间复杂度中存在相当多的歧义。例如，有人可能认为堆内存分配是O(1)。在这种情况下，仅重新分配数组就足以满足运行时要求。 - user4668606

@mcdowella，第一种方法很有道理。谢谢。第二种方法不行，至少不能只通过递增计数器来实现，因为比如在第二次遍历时（考虑列表中的第二个v的adj[v]），如果节点u的计数器读取为1，我们就无法知道这是第一次还是第二次。 - tarski

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sorin · Accepted Answer

您无需实际重置数组。

假设数组存储int。当且仅当mark[u] == v时，一个顶点被标记，其中v是当前顶点的索引或id。

当您移动到下一个顶点时，v的值会更改，并且所有数组中的条目都将计算为false，而无需更改数组中的值。