题1

题1

题目

下列关于图的存储结构的说法中, 错误的是 ( ).
A. 使用邻接矩阵存储一个图时, 在不考虑压缩存储的情况下, 所占用的存储空间大小只与图中的顶点数有关, 与边数无关
B. 邻接表只用于有向图的存储, 邻接矩阵适用于有向图和无向图
C. 若一个有向图的邻接矩阵的对角线以下的元素为 0 , 则该图的拓扑序列必定存在
D. 存储无向图的邻接矩阵是对称的, 所以只需存储邻接矩阵的下 (或上) 三角部分

分析

邻接表就是把这个点的出点全部都挂在这个点的后面

解

B
个顶点的图,若采用邻接矩阵表示,不考虑压缩存储,则存储空间大小为 正确。邻接表可用于存储无向图, 只是把每条边都视为两条方向相反的有向边, 因此需要存储两次, 错误。
因为邻接矩阵中对角线以下的元素全为 0,所以若存在 ,则必有 ,由传递性可知图中路径的顶点编号是依次递增的,假设存在环 ,由题设可知 ,矛盾, 所以不存在环, 拓扑序列必定存在, C 正确。D 显然正确。
注 意
若邻接矩阵对角线以下 (或以上) 的元素全为 0 , 则图中必然不存在环, 即拓扑序列一定存在, 但这并不能说明拓扑序列是唯一的。