🏷️ 知识点：拓扑序

下列关于图的存储结构的说法中，错误的是（ ）。

A. 使用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点数有关，与边数无关 B. 邻接表只用于有向图的存储，逆邻接表只用于无向图的存储 C. 若一个有向图的邻接矩阵的主对角线以下元素全为 0，则边只由小编号顶点指向大编号顶点，该图无环且必定存在拓扑序列（不保证唯一） D. 存储无向图的邻接矩阵是对称的，所以只需存储邻接矩阵的下（或上）三角部分

[tag_link]

正确答案：B

结论

错误的是 B。邻接表既可表示有向图，也可表示无向图；逆邻接表同样服务于有向图的入边访问。

推导

邻接矩阵始终按顶点对分配空间，未压缩时为 (O(n^2))，与边数无关。无向图矩阵对称，可只保存一侧三角区；若有向图矩阵主对角线以下全为 0，所有边均从小编号指向大编号，因而不可能成环，按编号升序即可得到一个拓扑序列。

易错点

不要把“邻接表”和“逆邻接表”误认为只适用于某一种图：邻接表通常记录出边，逆邻接表记录入边，二者主要用于有向图的不同访问方向；无向图也可用邻接表表示。