[What]数据结构与算法 -> 图

课程:王争 –> <数据结构与算法之美>

之前在 <算法图解> 对有个简单的理解,这次再来加深一下。

图的概念

graph.jpg

图的存储

邻接矩阵(Adjacency Matrix)

邻接矩阵使用二维数组的方式存储连接关系:

  • 对于无权重无向图来说: 若顶点i与j有边,则A[i][j] 和 A[j][i] 设为1
  • 对于无权重有向图来说: 若顶点i指向j,但顶点j不指向i,则仅将 A[i][j] 设为1
  • 对于有权重图来说: 则将对应边设为权重值即可
adj_save.jpg

优点:

  1. 基础数组存储,其操作效率高
  2. 方便使用矩阵运算来计算图

缺点:

  1. 无向图重复存储了一对关系,浪费空间
  2. 当顶点的边比较少时也很浪费空间

邻接表(Adjacency List)

使用数组和链表存储指向关系:

  • 数组存放顶点,链表表示每个顶点的关系
list_save.jpg

优点:

  1. 节省存储空间

缺点:

  1. 查找效率没有邻接矩阵高
Last Updated 2019-05-14 二 07:37.
Render by hexo-renderer-org with Emacs 26.1 (Org mode 9.1.14)