2019考研计算机数据结构考点：图的存储及基本操作

考研网

根据历年考试经验，数据结构所占分值为45分，所占分值比重较大;而且数据结构部分的知识比较难于理解，为方便考生更好地复习计算机专业课，新东方在线整理了考研计算机数据结构的有关内容，以供大家参考，希望对大家有所帮助。
    　　二、图的存储及基本操作
    1. 邻接矩阵表示法
    用一维数组存储图中顶点的信息;
    用矩阵(二维数组)表示图中各顶点之间的相邻关系。
   

    2. 邻接表法
   

    构造方法：
    与同一顶点邻接的所有邻接点构成一个单链表，用表结点描述;
    各链表设置表头结点，由头结点描述;
    各表头结点构成一个顺序表。
   

    3.邻接矩阵表示法与邻接表表示法的比较
    ①邻接矩阵是唯一的，邻接表不唯一;
    ②存储稀疏图用邻接表，存储稠密图用邻接矩阵;
    3求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便;
    ④判断是否是图中的边，邻接矩阵容易，邻接表最坏时间为O(n);
    5求边数e，邻接矩阵耗时为O(n2)，与e无关，邻接表的耗时为O(e+n);