6.2 选择题：表示法与复杂度

选择表示法要看密度和主要操作。矩阵空间固定 O(V²)，表空间与边相关；不能笼统说某一种“总是更好”。

手工状态

V=1000,E=2000 时邻接表明显节省空间；若需要百万次判边且图稠密，矩阵可能更合适。

结构与代码

多选：A 无向矩阵对称；B 有向邻接表长度给入度；C 矩阵枚举单点邻居 O(V)；D 邻接表总空间 O(V+E)。答案 A、C、D。

正确性依据

复杂度直接由需要扫描的存储范围得出：矩阵一整行，表中只扫描对应链。

错解反馈

把矩阵 O(1) 查边误写成 O(V)；忽略邻接表查特定边需扫描；无向表的边记录数忘乘2。

迁移训练

稀疏有向图频繁枚举入边，应如何设计？答案可同时维护正向和逆向邻接表，空间仍 O(V+E)。