3、讨论:邻接表与邻接矩阵有什么异同之处? 1.联系:邻接表中每个链表对应于邻接矩阵中的一行, 链表中结点个数等于一行中非零元素的个数。 2.区别: ①对于任一确定的无向图,邻接矩阵是唯一的(行列 号与顶点编号一致),但邻接表不唯一(链接次序 与顶点编号无关 ②邻接矩阵的空间复杂度为o(n2)而邻接表的空间复 杂度为o(n+e)。 3.用途: 邻接矩阵多用于稠密图的存储(e接近nn-1/2); 而邻接表多用于稀疏图的存储(e<<n2)13 3、讨论：邻接表与邻接矩阵有什么异同之处？ 1. 联系：邻接表中每个链表对应于邻接矩阵中的一行， 链表中结点个数等于一行中非零元素的个数。 2. 区别： ① 对于任一确定的无向图，邻接矩阵是唯一的（行列 号与顶点编号一致），但邻接表不唯一（链接次序 与顶点编号无关）。 ② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复 杂度为O(n+e)。 3. 用途： 邻接矩阵多用于稠密图的存储（e接近n(n-1)/2)； 而邻接表多用于稀疏图的存储（e<<n2)