请教大家一道关于邻接链表的算法题

设计一种O(V+E)的算法来将给定的一个图的邻接链表中包含的顶点(vertax)按由小到大的顺序排列。

V代表点，E代表边。
例如一个邻接链表原先是:
1: 4->3
2: 3->1->4
3: 4->2
4: 1
用完这个算法就变成：
1: 3->4
2: 1->3->4
3: 2->4
4: 1

不知道有没有大佬有思路的？感谢！

感觉就是一个LinkedList的排序问题啊。然后每个点都跑一遍。我暂时能想到的就是mergeSort了。

counting sort，复杂度O（E+V）是因为每个vertex都是独立的。或者理解为bucket sort也行。

补充内容 (2020-1-26 06:59):
打错，*每个vertex都是distinct的

zebsen 发表于 2020/01/26 22:57:38
counting sort，复杂度O（E+V）是因为每个vertex都是独立的。或者理解为bucket sort也行。

打错，每个vertex都是distinct的

zebsen 发表于 2020-1-26 22:57
counting sort，复杂度O（E+V）是因为每个vertex都是独立的。或者理解为bucket sort也行。

补充内容 (2020 ...

感谢回答！如果说总共有6个vertax，那么就需要用6次couting sort来完成吗？
couting sort的复杂度是O(n+k)，那么V在这里对应的是range k?E在这里对应的是number n?

milkkkmillkk 发表于 2020/01/29 01:13:51
感谢回答！如果说总共有6个vertax，那么就需要用6次couting sort来完成吗？
couting sort的...

k 对应V没错，n对应的是E+V, 因为adjacency list的space complexity是O(E+V)。所以总的来说time complexity是O(E+2V)=O(E+V)