🏷️ 知识点：邻接表建表复杂度

设某无向图中有n 个顶点和e 条边，则建立该图的邻接表的时间复杂度为()。

A. O(n+e) B.O(n²) C.O(ne) D.O(n³)

[tag_link]

正确答案：A

结论

答案为 A：建立邻接表的时间复杂度为 (O(n+e))。

推导

初始化 n 个顶点表结点并处理每条边（无向图处理两次），总操作数是 n 与 e 的线性和。

易错点

不要把邻接表建表误写成矩阵的 (O(n^2))；只有扫描整张矩阵才有该复杂度。