algorithm - 从一束边创建邻接列表的复杂性？

Question

我正在创建一种算法，可以从边列表构建邻接列表。

例如，如果数据输入是：

1 2
1 8
2 8
3 5
3 1
4 5
4 6
5 2
5 9
6 4
6 8
7 4
7 10
8 4
8 6
9 4
9 5
10 7
10 3

输出将是：

1: 8 4 6
2: 4 6
3: 9 2 8
4: 2 9 8
5: 8 4
6: 5 4
7: 5 6 3
8: 5 6 4
9: 5 6 2
10: 4 5 1

该算法显然受顶点和边数的限制，所以最初我认为它是 O(v + e)。但是我只能通过在带有二维数组的 for 循环中实现 for 循环来使程序工作，我认为这会导致 O(N^2) 的复杂性。

谁能帮助我更好地理解？

Answer 1

这在很大程度上取决于您使用哪种数据结构来存储从顶点到相邻顶点列表的地图。遍历边列表当然会有时间复杂度 O(e)。任何更大的时间复杂度都来自于在地图中找到一个顶点所需的时间以及将一个新项目插入到顶点的相邻顶点列表中所需的时间。如果您使用的是平面数组，那么您可能具有 O(v*e) 复杂度（对于每条边，循环遍历顶点列表以找到所需的顶点），但是通过使用哈希表或树可以大大改善这一点数据结构，为您提供更好的查找性能。