🏷️ 知识点：图的稀疏存储
课后题 年第 28 题
数据结构
选择题
设某无向图中有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))；只有扫描整张矩阵才有该复杂度。
设某无向图中有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))；只有扫描整张矩阵才有该复杂度。