图及其应用场景

一、图的一些基本概念

图是一种非线性的数据结构，具有如下一些基本概念：

• 图中的各个元素称之为顶点；
• 顶点和其它任意顶点之间的关联关系称之为边；
• 一个顶点的边的数量称之为度；
• 图可以分为无向图和有向图，微信中的朋友关系就是一种无向图，微博中的关注与被关注的关系就是一种有向图；
• 在有向图中，指向当前顶点的边的个数称之为入度，由当前顶点指出去的边的个数称之为出度；
• 图中每条边都有权重的就是带权图，QQ亲密度关系的表示就是一种带权无向图；

二、图的存储

2.1 邻接矩阵

本质上是一个超大的二维数组A，在无向图中，如果顶点i和j之间有边，那么A[i][j]和A[j][i]就置为1；在有向图中，如果顶点i指向顶点j，那么A[i][j]就置为1；对于带权图，数组相应位置存放的就是权重数值。

三种图的邻接矩阵存储法

优点：实现起来比较简单，使用过程中也比较直观。当要判断某两个顶点是否有关系的时候，直接利用数组的随机访问特性就能很高效率地得到答案。

缺点：比较浪费存储空间。比如在无向图中，顶点i和顶点j之间有关系，其实只要存储A[i][j]即可，存储空间浪费了一半；还有如果遇到稀疏图，比如顶点很多，但是有边的就只有几个，那么二维矩阵数组中将会出现大量的0。

2.2. 邻接表

采用数组加上链表的形式，有点类似于散列表中的链表法。数组中存放的是每一个顶点，每个顶点对应的链表中存放的是该顶点指向的顶点。

有向图的邻接表存储法

优点：比较省空间。

缺点：查询效率比较慢，特别是当链表很长的时候，可能要借助平衡二叉树（红黑树）的优化方案来提速；

三、图的搜索算法

搜索算法的目的是为了求解一个顶点到另外一个顶点的路径。

3.1 广度优先搜索

直观地讲，广度优先搜索就是一种地毯式地层层推进搜索策略，先查找距离当前顶点最近的，然后逐步推向最外层的。

广度优先搜索过程示意图

3.2 深度优先搜索

直观地讲，深度优先搜索就是一种走迷宫式地一条路走到黑的搜索策略，就是先从当前顶点开始选择一条路一直走到头为止，然后退回一步，继续寻找其它路径。

深度优先搜索过程示意图

3.3 A*算法

A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。笔者曾经将上海地铁站所有站点都录入数据库，然后借助该算法求解A站到B站的最短路径，并输出中途经过的所有站点名称。

四、总结

广度和深度优先搜索算法既可以作用于无向图，也可以作用于有向图，但它们是比较暴力的搜索算法，仅适用于图不是很大的场景。

在实现上，广度优先搜索算法需要借助队列来实现，深度优先搜索算法是使用了回溯的算法思想，可以使用递归来实现，即使用栈来实现。