图的表示

Tuesday, May 21, 2019

如何理解图

图是一种较为复杂的非线性表结构

  • 图的元素叫作顶点。
  • 图与其他顶点建立连接关系,称为边。

file

  • 每个顶点周围有多个顶点,称为度。
  • 在有向图中,把度分为入度和出度,入度是指有多少个顶点指向该顶点,出度反之。
  • 比如微信好友关系的存储是用无向图,微博是用有向图。

file

  • 如果还要有亲密度功能,比如QQ的亲密好友,这里用到带权图。

file

如何存储图

邻接矩阵存储方法

  • 最直观的存储方式,邻接矩阵,用一个二维数组来实现。
  • 对于无向图来说,如果顶点i与顶点j有边,就将A[i][j]和A[j][i]标记为1。
  • 对于有向图来说,如果有一条箭头从顶点i指向j的边,则将A[i][j]标记为1。

file

  • 对于无向图来说,如果A[i][j]等于1,则A[i][j]也等于1,相当于一半空间被浪费了。
  • 如果是稀疏图,就是顶点很多,但每个顶点的边不多,那邻接矩阵更加浪费空间。比如微信有几亿用户,都是顶点,但好友一般只有几百个,用邻接矩阵的话,大部分空间都被浪费了。
  • 邻接矩阵因为完全基于数组,所以访问速度很快,获取两个顶点的关系很高效,也方便进行计算,因为可以转换为矩阵之间的计算。

邻接表存储方法

  • 邻接表有点类似散列表,每个顶点对应一条链表,链表存储的是该顶点连接的其他顶点。

file

  • 我们也可以将邻接表中的链表换成平衡二叉查找树,比如红黑树。

如何存储微博的社交网络关系

  • 因为社交网络是稀疏图,所以用邻接表来存储。
  • 还得加一个逆邻接表,因为邻接表查用户关注了哪些人比较容易,但是很难去查找被哪些人关注了,也就是粉丝列表,用逆邻接表存储用户被关注的信息。

file

数据结构-算法

Linux常用命令

堆排序(上)