【数据结构与算法】图

港控/mmm° 2022-11-30 04:20 167阅读 0赞

**一：如何理解“图”**  
1，图和树一样都是非线性表数据结构，和树不同的是图是一种更加复杂的非线性表结构  
2，树中的元素称之为节点，图中的元素则称之为顶点。  
3，顶点可以与任意其他顶点建立关联，这种建立的关系叫做边，与顶点相连接的条数叫做顶点的度。  
4，图可以分为有向图和无向图两种，有向图的边有方向。  
5，在有向图中，度可以分为入度和出度（Out-degree）  
6，带权图：在带权图中，每条边都有一个权重

**二：邻接矩阵存储方法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

1，图最直观的一种存储方法是：邻接矩阵（Adjacency Matrix），邻接矩阵的底层依赖一个二维数组。

2，用邻接矩阵来表示一个图，虽然简单，直观，但是浪费存储空间。  
①：对于无向图的二维数组中，如果将其对角线划分为上下两部分，那我们只需要利用上面或者下面这样的一半的空间就足够了，另一半白白浪费掉了。  
②：若存储的是稀疏图（Sparse Matrix），即顶点很多，但每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间了。  
3，用邻接矩阵存储的优点：  
①：存储方式简单，直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。  
②：其次是计算方便。因为，可以将很多图的运算转换成矩阵之间的运算。如求解最短路径问题时会提到一个Floyd-Warshall算法，就是利用矩阵循环相乘若干次得到结果。  
**三：邻接表存储方法**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

1，邻接表（Adjacency List）可以解决邻接矩阵存储方式比较浪费内存空间的问题  
2，邻接矩阵存储起来比较浪费空间，但使用比较节省时间，邻接表存储与之相反。  
如图中，如果要确定是否存在从顶点2到顶点4的边，就需要遍历顶点2对应的链表，看那条链表中是否存在顶点4。但链表的存储方式对缓存不友好。  
3，我们可以将邻接表中国的链表改成平衡二叉查找树，实际开发中国还可选用红黑树。这样可以快速查找两个顶点之间是否存在边了。

**四：图的应用**  
**如何存储微博，微信、QQ等社交网络中的好友关系？**

1.  微博，微信是两种“图”，前者是有向图，后者是无向图。
2.  QQ无向图 权重亲密度

数据结构是为算法服务的，所以具体选择哪种存储方法，与期望支持的操作有关系。针对微博的用户关系，需要支持：  
 判断用户A是否关注了用户B;  
 判断用户A是否是用户B的粉丝  
 用户A关注用户B；  
 用户A取消关注用户B；  
 根据用户名称的首字母排序，分页获取用户的粉丝列表；  
 根据用户名称的首字母排序，分页获取用户的关注列表。

3 。因为社交网络是一张稀疏图，使用邻接矩阵存储比较浪费存储空间，所以使用邻接表来存储。  
4，但用一个邻接表来存储这种有向图是不够的，查找某个用户关注了哪些用户非常容易，但是如果想要知道某个用户都被哪些用户关注了，是非常困难的。因此，需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储的是用户的被关注关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

对应到图上，邻接表中，每个顶点的链表中，存储的就是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。

1.  基础的邻接表不适合快速判断两个用户之间是否是关注与被关注的关系。  
    因为我们需要按照用户名称的首字母排序，分页来获取用户的粉丝列表或者关注列表，用跳表这种结构再合适不过了。这是因为，跳表插入、删除、查找都非常高效，时间复杂度是 O(logn)，空间复杂度上稍高，是 O(n)。最重要的一点，跳表中存储的数据本来就是有序的了，分页获取粉丝列表或关注列表，就非常高效。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
    1 内存中用邻接表；  
    2 要持久化存储就用数据库  
    2 超大图 并且涉及大量图计算。用专业的图数据库

[笔记整理来源： 王争 数据结构与算法之美][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/f7d1e83da1d848eab43f3d3be005a560.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/9af412cba34d4e5f9daea07b88b9d0a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/bbcd28cf89d847fe979294fd23c1f39e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/3f311b8285ac4a7d92e5dbae8d8a71bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/15f41a53d602498cbf635e77e7f08ad2.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png