一、图的一些基本概念
图是一种非线性的数据结构，具有如下一些基本概念：
- 图中的各个元素称之为顶点；
- 顶点和其它任意顶点之间的关联关系称之为边；
- 一个顶点的边的数量称之为度；
- 图可以分为无向图和有向图，微信中的朋友关系就是一种无向图，微博中的关注与被关注的关系就是一种有向图；
- 在有向图中，指向当前顶点的边的个数称之为入度，由当前顶点指出去的边的个数称之为出度；
- 图中每条边都有权重的就是带权图，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站的最短路径，并输出中途经过的所有站点名称。
四、总结
广度和深度优先搜索算法既可以作用于无向图，也可以作用于有向图，但它们是比较暴力的搜索算法，仅适用于图不是很大的场景。
在实现上，广度优先搜索算法需要借助队列来实现，深度优先搜索算法是使用了回溯的算法思想，可以使用递归来实现，即使用栈来实现。
网友评论