2019考研计算机数据结构考点：图的存储及基本操作
根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。二、图的存储及基本操作
1. 邻接矩阵表示法
用一维数组存储图中顶点的信息;
用矩阵(二维数组)表示图中各顶点之间的相邻关系。
http://file.koolearn.com/24061545008455.png
2. 邻接表法
http://file.koolearn.com/42121545008455.png
构造方法：
与同一顶点邻接的所有邻接点构成一个单链表，用表结点描述;
各链表设置表头结点，由头结点描述;
各表头结点构成一个顺序表。
http://file.koolearn.com/1341545008455.png
3.邻接矩阵表示法与邻接表表示法的比较
①邻接矩阵是唯一的，邻接表不唯一;
②存储稀疏图用邻接表，存储稠密图用邻接矩阵;
3求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便;
④判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n);
5求边数e，邻接矩阵耗时为O(n2)，与e无关，邻接表的耗时为O(e+n);
页:
[1]