邻接表的空间复杂度和时间复杂度

邻接表是一种常用的图的表示方法，它使用链表来表示图中每个顶点的邻接关系。邻接表的空间复杂度和时间复杂度如下：

空间复杂度：
邻接表的空间复杂度取决于图中顶点的个数n和边的个数m。在最坏情况下，每个顶点都与其他所有顶点相邻，那么邻接表的空间复杂度为O(n+m)。

时间复杂度：
1. 查找某个顶点的邻接点：在邻接表中查找某个顶点的邻接点的时间复杂度取决于该顶点的度数（即与之相邻的边的个数）。在最坏情况下，需要遍历该顶点的所有邻接点，时间复杂度为O(度数)。
2. 插入一条边：在邻接表中插入一条边的时间复杂度为O(1)，只需要在对应的链表中插入一个节点。
3. 删除一条边：在邻接表中删除一条边的时间复杂度为O(度数)，需要遍历对应的链表找到要删除的节点并删除。

综上所述，邻接表的空间复杂度为O(n+m)，查找某个顶点的邻接点的时间复杂度为O(度数)，插入和删除边的时间复杂度也与度数相关。