相关概念
-
社交网络就是典型的图应用。
无向图
- 顶点（vertex）：图中的元素。
- 边（edge）：图中的一个顶点可以与其他任何顶点建立连接关系，这种建立的关系叫边。
-
度（degree）：跟顶点相连接的边的条数。是无向图中的概念。
微信的互加好友就是无向图的应用
有向图
- 入度（In-degree）：表示有多少边指向这个顶点。有向图中的概念。
-
出度（Out-degree）：表示有多少条边是以这个顶点为起点指向其他顶点。也是有向图中的概念。
微博的单向关注就是有向图的应用
带权图
-
带权图：图中的每条边都有一个权重。
QQ好友的亲密度的记录就是带权图的应用
图的存储方法
1.邻接矩阵存储方法(Adjacency Matrix)
- 邻接矩阵底层依赖一个二维数组。
对于无向图来说，如果顶点ｉ与顶点ｊ之间右边，就将A[i][j]和A[j][i]标记为1。
对于有向图来说，如果顶点i到顶点j之间有一条箭头从顶点ｉ指向顶点ｊ的边，那么将A[i][j]标记为1；如果没有ｊ到ｉ的边，将顶点A[j][i]标记为0，有的话也标记为1。
对于带权图，数组中就存相应的权重。 -
缺点：浪费存储空间
可以将无向图用对角线划分为上、下两部分，我们只需要利用上面或下面一半的空间就足够了。另一半浪费。
如果我们村稀疏图（Sparse Matrix），顶点很多，但每个顶点的边不多，那么临街矩阵的方式浪费了大量空间。 -
优点：
存储方式简单、直接，基于数组，获取两个顶点关系时很高效。
方便计算，可以将很多图的运算转化为矩阵之间的运算。
2.邻接表存储方法(Adjacency List)
- 类似于散列表，每个顶点对应一个链表，链表中存储的是与这个顶点相连接的其他顶点。有向图里面存的是顶点指向的其他顶点；无向图里面存的是和本顶点有边相连的其他顶点。
- 邻接矩阵存储起来比较费时间，但使用起来比较节省时间；邻接表正好与它相反，这也正是空间换时间的思想。
- 优点：节省存储空间
-
效率：没有邻接矩阵高，针对这个问题对邻接表的优化：
可以将邻接表顶点对应的链表改为平衡二叉树，如红黑树。也可以换为其他动态数据结构，比如跳表，散列表等。还可将链表改成有序动态数组，可以通过二分查找的方法快速定位两个顶点之间是否存在边关系。
网友评论