查询图中指定节点邻接节点的时间复杂度是多少？

这个问题的答案取决于图的存储结构，分两种常见情况分析：

邻接矩阵存储 #

如果图用V×V的邻接矩阵存储，查询指定节点的邻接节点数量时，必须遍历该节点对应的整行（共V个元素），判断每个位置是否存在边。这种场景下，时间复杂度确实是O(V)，和你的判断一致。比如你举的V=5的例子，就需要检查节点1对应的5个矩阵元素，统计其中代表边的数量。

邻接表存储 #

如果图用邻接表存储（每个节点对应一个列表，直接记录其邻接节点），那查询操作的时间复杂度是O(deg(v))——其中deg(v)是目标节点v的度数（也就是邻接节点的数量）。

• 最好情况：节点v没有邻接节点，时间复杂度O(1)
• 最坏情况：节点v和其他所有节点都相连（deg(v)=V-1），时间复杂度退化为O(V)
• 稀疏图场景下，这个操作的耗时会远低于O(V)

你提到的「时间复杂度不应为O(E)」是完全正确的——不管用哪种存储结构，查询单个节点的邻接数量都不需要遍历图中所有边，所以O(E)的说法不成立。

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