邻接表的分类与特点

邻接表是图论中常用的一种数据结构，也是图论中常用的一种表示图的方法。它是一种用于表示有向图或无向图的方式，以及与每个顶点相关联的连通边的相邻表形式。邻接表可以简化对图结构的许多操作，使其更易于处理。本文将从邻接表的分类、特点以及使用场景等角度进行分析。

分类

邻接表通常有两种分类方式，分别是静态邻接表和动态邻接表。

1.静态邻接表：静态邻接表是指邻接表的大小在构建之后不适合改变的邻接表。我们在初始设定好每个节点的度数为d后，就可以根据每个节点的度数来确定邻接表相应的大小。静态邻接表的优点是 动态创建新节点时，不需要重新分配内存，从而保证了空间的利用率。但静态邻接表的缺点是无法扩展和缩小图的大小，当需要加入或删除节点时，只能重新构建一个新的邻接表，这对于大图而言操作十分耗时。

2.动态邻接表：动态邻接表是可以动态地增加或删除节点的邻接表。当我们需要向邻接表中添加新节点时，可以直接分配空间，而无需重新构建整个邻接表。动态邻接表的缺点是分配或释放空间时，需要进行内存的拷贝，因此，其时间复杂度会较高。但是当需要操作的图非常大时，动态邻接表相较于静态邻接表而言，具有更高的灵活性和效率。

特点

邻接表的特点是具有较好的存储效率和查找效率。

1.空间效率:在邻接表中，以列表的形式存储节点的邻接表，如此一来，边的数量对于存储空间的影响是O（n+m），其中n和m分别为节点数和边数。相较于邻接矩阵的空间代价为O（n^2）而言，空间效率更高。

2.时间效率:在邻接表中，我们可以快速地查找某个节点的邻居节点，其复杂度为O（d），其中d是该节点的度数。当一个节点的度数比较小的时候，邻接表的时间效率可以和邻接矩阵媲美，当一个节点的度数较大的时候，邻接表就比邻接矩阵具有更好的时间效率。由此可见，邻接表和邻接矩阵各有千秋。

使用场景

邻接表适用于边数相对于节点数非常小的稀疏图。此外，邻接表的使用场景还有以下几个方面：

1. 基于邻接表的遍历算法：使用邻接表结构可以以相同的算法复杂度遍历图，因此在深度优先搜索和广度优先搜索等遍历算法方面，邻接表离不开它的作用。

2. Dijkstra算法：Dijkstra算法用于找出两个节点之间的最短路径。邻接表是实现Dijkstra算法的首选数据结构。它可以在O（E+VlogV）的时间复杂度下完成计算任务。

3. Prim算法：Prim算法用于找出一张连通加权图的最小生成树。在实现Prim算法时，邻接表也是一个非常好的选择。