本文共 2478 字，大约阅读时间需要 8 分钟。

图的介绍

1. 图 ( Graph )，是一种复杂的非线性表结构，图中的元素成为顶点 ( vertex )，每一个顶点可以与任意其他顶点建立连接关系，这种关系叫作边 ( edge )，与顶点相连接的边的条数，称为顶点的度 ( degree )；

下图可以表示，微信好友之间的关系

2. 根据图的边，是否有单向性，分为有向图和无向图，在有向图中，度分为入度和出度，入度是有多少条边指向顶点，出度是有多少条边以该顶点为起点；

下图可以表示微博用户之间的关注关系，因为有单向性

3. 带权图 ( weighted graph )，每条边都有一个权重 ( weight )，可以通过这个权重来表示顶点之间的联系程序；

下图中，可以表示 qq 好友间的亲密度

图的存储

1. 一种存储方法是邻接矩阵（Adjacency Matrix），即使用一个二维数组存储；

如果是无向图，如果顶点 i 与顶点 j 之间有边，就将 A[i][j]和 A[j][i]标记为 1	如果是有向图，如果有从顶点 i 指向顶点 j 的边，就将 A[i][j]标记为 1，同理，如果有从顶点 j 指向顶点 i 的边，就将 		A[j][i]标记为 1	如果是带权图，数组中就存储相应的权重，而不是数字 1

2. 邻接矩阵的存储方式，有可能很浪费空间，因为对于无向图，二维数组对角线一半的数据即可表示，并且如果顶点很多，但每个顶点的边有限，如 微信几亿用户，只有几百个好友，用二维数组表示，就会极大的浪费空间，且几乎不可能实现；

邻接矩阵存储的优点是		存储方式简单、直接		获取顶点间关系时，非常高效		方便计算，可以将很多图的运算，转换成矩阵之间的运算

3. 另一种图的存储方法是邻接表（Adjacency List），使用数组加链表的方式存储，数组每个元素存储一个链表，链表的头节点是各个顶点，其他节点依次是与该顶点有边相连的顶点，如果是有向图，就只有从该顶点的出度连接的顶点；
   
4. 邻接表的存储，比较节省存储空间，使用比较耗时，如果要查询是否存在从 顶点2 到顶点 4 的关系，就需要遍历顶点2 存储的链表，是否存在节点4，要想改善邻接表的查找效率，可以将链表改造成平衡二叉树等查找效率高的数据结构；

图的使用场景

1. 微博用户之间的关注关系，如何存储和获取，首先内存中用图来表示，采用邻接矩阵，空间浪费大，可以使用邻接表，并且如果要获取用户的粉丝列表，即哪些用户关注了自己，可以额外维护一个逆邻接表；

2. 如下图，邻接表，直接存储用户的关注关系，逆邻接表，直接存储用户的粉丝列表，并且，如果要查找一个用户是否关注另一个用户，链表查找时间复杂度高，因此可以将链表数据采用红黑树，跳表，散列表，或者有序动态数组存储；

   

3. 对于链表的替代方案，因为要经常有序输出关注列表，因此可以采用跳表实现，跳表中数据本身有序；

4. 再考虑一个问题，单机内存是无法容纳如此庞大的关系数据，因此需要将邻接表划分为多份存储，对每个顶点，使用哈希算法，计算哈希值，然后对机器个数取余，得到的就是顶点的存储机器，所以但查看某个顶点的关系时，首先哈希计算得到机器编号，去相应的机器查询；

5. 该用户关注关系图，也需要持久化存储，可以在数据库中建立一张表，有 user_id 和 follow_id 的字段，分别建立索引；

   

广度优先搜索算法

1. 基于图的数据结构，解决从起始节点到终止节点的路径问题，即用户的关系度，一个用户如何通过朋友的朋友，朋友的朋友的朋友，来找到另一个人；

2. 广度搜索，是逐层访问，先获取一个顶点的所有直接关系顶点，然后通过第一步获取的顶点向外层获取去，编程上，借助队列 queue，记录将要访问的外层顶点，借助数组 visited，记录已经访问的顶点，避免重复访问，借助数组 prev 记录搜索路径，如下标 2 的值，就表示顶点 2 是如何被访问的；

3. 第一步，起始顶点入队，visted[0] = 1 表示顶点 0 已经被访问；第二步，顶点 0 出队，并将出队顶点所有关联节点入队，即 1 和 3 出队，visted[ 1 ] = 1，visited[ 3 ] = 1，表示顶点 1 和顶点 3 都被访问了，同时 pre[1] = 0， pre[3] = 0，表示要访问顶点 1 和 顶点 3 都需要先访问顶点 0；

   

4. 然后顶点1 出队，将顶点1 直接关联的顶点 2 和顶点 4入队，并将 visited[2] 和 visited[4] 赋值为 1，pre[2] 和 pre[4] 赋值为1；

   

5. 然后队列头顶点 3 出队，因为顶点 3 没有直接联系的顶点，所有该操作，queue 和 visited，prev 均没有改变，然后顶点 4 出队，顶点 5 和 6 入队，visited[ 5 ] 和 visited [ 6 ] 赋值为1，pre[5] 和 pre[6] 均赋值为4，然后顶点 2 出队，也没有相连顶点，然后顶点 5 出队，找到顶点 7，visted[5] 为 1，pre[7] = 5，搜索结束，

   

6. 最后找到节点 7，通过数组 prev，反向打印非 -1 的数据，即得到路径 75410，反向即 01457，找到起点 0 到终点 7 的路径，并且广度搜索找到的路径，就是一条最短路径；

深度优先算法

1. 深度优先算法，也是用来查找一个节点到另一个节点的路径，但得到的结果不一定是最短路径；

2. 算法思路是，每到一个岔路口，即一个顶点有多个其他关联顶点时，任选一个顶点进行搜索，如此，如果搜索结束都没有找到另一个节点，回退到上一个岔路口，走另一个岔路，如此回溯，直到最终找到另一个节点，就得到了路径；

3. 同样编程中使用到 visited 数组和 prev 数组，下图是整个回溯过程，虚线表示回溯步骤，非常适合用递归实现；

   

4. 广度和深度优先搜索的时间复杂度，都是是 o( E )，空间复杂度都是是 o( V )，E 表示图的边数，V 表示顶点总数；

应用

1. 获取好友的三度关系好友，即好友的好友的好友列表，可以使用广度搜索算法，额外通过一个数组记录每个顶点与起点的距离；

转载地址：http://wpfin.baihongyu.com/