🏷️ 知识点：入度与出度

对邻接表的叙述中，（　　）是正确的。

A. 无向图的邻接表中，第 i 个顶点的度为第 i 个链表中结点数的两倍 B. 邻接表比邻接矩阵的操作更简便 C. 邻接矩阵比邻接表的操作更简便 D. 求有向图顶点的度，必须遍历整个邻接表

[tag_link]

正确答案：D

结论

选 D。

推导

无向图邻接表中每条边在两个链表各出现一次，所以第 i 个链表的结点数就是顶点 i 的度，不需要再乘 2。有向图顶点的出度可扫描自身链表，但入度要检查所有边表；求总度时必须遍历整个邻接表。

易错点

邻接表与邻接矩阵没有“所有操作都更简便”的绝对关系，应按操作类型和图的稠密程度选择。