考研网 发表于 2018-12-19 19:20:42

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]
查看完整版本: 2019考研计算机数据结构考点:图的存储及基本操作