邻接矩阵与邻接表时间复杂度相关疑问

问题1：邻接矩阵操作的时间复杂度差异 #

• 判断u和v是否相邻（Are adjacent(u,v)）：邻接矩阵就是n×n的二维数组，matrix[u][v]直接存着u和v之间有没有边（比如用1代表有、0代表没有）。直接通过下标访问这个位置就能得到结果，不用遍历其他元素，所以时间复杂度是O(1)。
• 获取u的关联边（incident edges(u)）：要找出所有和u相连的节点，必须把u对应的整行n个元素全部扫一遍，逐个检查每个位置是否存在边。哪怕这一行大部分位置都是0（没边），也得挨个确认才能找全所有关联边，所以时间复杂度是O(n)。你的推测完全正确。

问题2：邻接表判断相邻的时间复杂度 #

邻接表里每个节点对应一个存着它邻接节点的链表（或动态数组）。要判断u和v是否相邻，要么遍历u的邻接表找v，要么遍历v的邻接表找u。为了少跑几次，肯定选更短的那个邻接表——也就是度数更小的节点对应的表。

这个O(min{degree(u), degree(v)})是最坏情况的时间复杂度，不是最优情况：

• 最优情况是刚遍历第一个元素就找到目标，时间复杂度是O(1)；
• 但我们说数据结构操作的时间复杂度时，默认指的是最坏情况下的开销，所以这里取遍历较短邻接表的最坏次数，也就是度数更小的那个值对应的时间复杂度。

内容的提问来源于stack exchange，提问作者user22712878