图的存储

邻接矩阵法 无向图的邻接矩阵 1、一定是一个对称矩阵
2、每一行(列)的非零元素个数正好是顶点的度
有向图的邻接矩阵 1、每一行的非零元素个数对应出度
2、每一列的非零元素个数对应入度
共性 1、邻接矩阵容易确定两个点是否相连但是难以确定边数(需要逐行列遍历)
2、邻接矩阵适合存储稠密图
链接表法 存储空间 1、无向图的存储空间为顶点数加边数乘2,有向图则为顶点数加边数
特性 1、适合存储稀疏图
2、很容易找到一个顶点的所有邻边,而邻接矩阵则需要遍历一行
3、但是要确定给定的两个顶点之间是否存在边邻接矩阵则可以快速找到
4、链接表表示不唯一
手绘图 【图的存储】图的存储
文章图片

    推荐阅读