algorithm - 对于给定的图 G = (V,E)，如何在 O(E+V) 时间内对它的邻接表表示进行排序？

Question

因为我们知道表示顶点的整数可以取[0,...,|V|-1] 范围内的值，所以我们可以使用计数排序对每个条目进行排序O(V) 时间的邻接表。

因为我们有 V 个列表要排序，所以这会给我们一个 O(V^2) 时间算法。我不知道我们如何将其转换为 O(V+E) 时间算法...

Answer 1

事实上，您需要对 E 个元素进行排序 - 边数。因此，您对 O(V^2) 的估计不太正确。您可以根据它包含的边数 在线性时间内对每个邻接列表进行排序。由于总共有 E 条边，因此对所有列表进行排序的复杂度将为 O(E)。当然，因为你有 V 列表，你不能低于 O(V)，因此估计 O(V +E) .