数据结构 · 邻接表

近年来 408 数据结构真题中，与「邻接表」相关的题目共 5 道，累计 18 分。

邻接表求入度：需遍历所有边链表，复杂度 O(|E|)

图基本概念邻接表

拓扑排序复杂度：邻接表存储时拓扑排序的时间复杂度为 O(n+e)

邻接表拓扑排序

> **总思路**：题面看似考网络，其实考的是**图的抽象 + 邻接表设计 + Dijkstra**——把 4 个路由器和 4 个直连子网当作图的顶点，链路当作

图基本概念邻接表Dijkstra 最短路径

BFS 遍历复杂度：邻接表存储时广度优先搜索的时间复杂度

邻接表广度优先搜索

图的基本概念：回路与简单路径的区别、稀疏图存储选择

邻接矩阵邻接表拓扑排序