图（Graph）是一种比树更加复杂的非线性表结构。图中的元素我们叫做顶点（vertex），图中的一个顶点可以与任意其他顶点建立连接关系，我们把这种建立的关系叫做边（edge）。
社交网络就是一个非常典型的图结构。以微信举例，我们可以把每个用户看作一个顶点，如果两个用户之间互加好友，那就在两者之间建立一条边。所以整个微信的好友关系就可以用一张图来表示。其中，每个用户有多少个好友，对应到图中就叫做顶点的度（degree），就是跟顶点相连接的边的条数。
微博的社交关系比微信更加复杂一点，微博允许单向关注。也就是 A 关注了 B，但 B 可以不关注 A。此时，我们可以把上面的图结构改造一下，引入边的“方向”的概念。如果 A 关注了 B，我们就在图中画一条从 A 到 B 的带箭头的边来表示边的方向。如果 A 和 B 互相关注，那我们就画一条从 A 指向 B 的边，再画一条从 B 指向 A 的边。我们把这种边有方向的图叫做有向图。以此类推，我们把边没有方向的图就叫做无向图。
无向图中有度这个概念，表示一个顶点有多少条边。在有向图中，我们把度分为入度和出度。顶点的入度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。对应到微博的例子，入度就表示有多少粉丝，出度就表示关注了多少人。
我们再来看另一种社交软件：QQ。QQ 中的社交关系要更加复杂，它还记录了两个用户之间的亲密度，如果两个用户经常往来，那亲密度就比较高；如果不经常往来，亲密度就比较低。那如何在图中记录这种好友关系的亲密度呢？这里就要用到带权图。在带权图中，每条边都有一个权重（weight），我们可以通过这个权重来表示 QQ 好友间的亲密度。
存储方式
1. 邻接矩阵
图最直观的一种存储方法就是邻接矩阵（Adjacency Matrix），邻接矩阵的底层依赖一个二维数组。
- 对于无向图来说，如果顶点 i 与顶点 j 之间有边，我们就将 A[i][j] 和 A[j][i] 标记为 1
- 对于有向图来说，如果顶点 i 到顶点 j 之间，有一条箭头从顶点 i 指向顶点 j 的边，那我们就将 A[i][j] 标记为 1。同理，如果有一条箭头从顶点 j 指向顶点 i 的边，我们就将 A[j][i] 标记为 1。
- 对于带权图，数组中就存储相应的权重。
用邻接矩阵来表示一个图，虽然简单、直观，但比较浪费存储空间。因为对于无向图来说，如果 A[i][j] 等于 1，那 A[j][i] 也肯定等于 1。实际上，我们只需要存储一个就可以了。还有，如果我们存储的是稀疏图（顶点很多，但每个顶点的边并不多），那邻接矩阵的存储方法就更加浪费空间了。
但邻接矩阵的存储方法也不是没有优点。首先存储方式简单、直接，因为基于数组，所以在获取两个顶点的关系时非常高效。其次，用邻接矩阵存储图的另外一个好处是方便计算。因为用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵间的运算。比如求解最短路径问题，就是利用矩阵循环相乘若干次得到结果。
2. 邻接表
针对邻接矩阵比较浪费内存空间的问题，我们来看另外一种图的存储方法，邻接表（Adjacency List）。邻接表的每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。下图是一个有向图的邻接表存储方式，每个顶点对应的链表里面，存储的是指向的顶点。无向图也是类似的，不过每个顶点的链表中存储的，是跟这个顶点有边相连的顶点。
代码实现：
public class Graph {/*** 邻接表，数组下标代表顶点元素，链表里保存边的信息*/private final List<Integer>[] adj;public Graph(int capacity) {adj = new List[capacity];for (int i = 0; i < capacity; i++) {adj[i] = new ArrayList<>();}}/*** 添加边，无向图一次保存两条边，有向图一次保存一条边*/public void addEdge(int start, int target) {adj[start].add(target);adj[target].add(start);}}
上面说到，邻接矩阵存储起来比较浪费空间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但使用起来比较耗费时间。如上图所示，如果我们要确定，是否存在一条从顶点 2 到顶点 4 的边，那我们就要遍历顶点 2 对应的那条链表，看链表中是否存在顶点 4。而且，链表的存储方式对缓存不友好。所以，比起邻接矩阵的存储方式，在邻接表中查询两个顶点之间的关系就没那么高效了。
在基于链表法解决冲突的散列表中，如果链表过长，为了提高查找效率，我们可以将链表换成其他更高效的数据结构，比如平衡二叉查找树等。所以，我们也可以对邻接表中的链表进行同样的改造。实际开发中，我们可以选择用红黑树或者跳表来代替链表。这样，我们就可以更加快速地查找两个顶点之间是否存在边了。除此之外，我们还可以将链表改成有序动态数组，这样可以通过二分查找的方法来快速定位两个顶点之间否是存在边。
用一个邻接表来存储有向图是不够的。因为我们去查找某个用户关注了哪些用户是非常容易的，但如果要想知道某个用户都被哪些用户关注了，是非常困难的。因此我们额外还需要一个逆邻接表。邻接表中存储了用户的关注关系，逆邻接表中存储了用户的被关注关系。对应到图上，邻接表中，每个顶点的链表中，存储的是这个顶点指向的顶点，逆邻接表中，每个顶点的链表中，存储的是指向这个顶点的顶点。如果要查找关注了哪些用户，我们可以从邻接表中查找；如果要查找被哪些用户关注，我们可以从逆邻接表中查找。
搜索算法
我们知道，算法是作用于具体数据结构之上的，深度优先搜索算法和广度优先搜索算法都是基于图这种数据结构的。因为图这种数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成图。图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。需要说明一下，深度优先搜索算法和广度优先搜索算法，既可以用在无向图，也可以用在有向图上。下面统一针对无向图来讲解。
1. 广度优先搜索（BFS）
广度优先搜索（Breadth-First-Search）其实是一种地毯式，层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。搜索过程如下图所示。
代码实现：
/*** 广度优先搜索，实际上，这样求得的路径就是从s到t的最短路径** @param s 起始顶点* @param t 终止顶点*/public void bfs(int s, int t) {if (s == t) {return;}// 用来记录已经被访问的顶点，避免顶点被重复访问boolean[] visited = new boolean[adj.length];visited[s] = true;// 用来存储自身已经被访问了的，但其相连的顶点还没有被访问到的顶点Queue<Integer> queue = new LinkedList<>();queue.add(s);// 用来记录搜索路径，初始值都设为-1，表示没有元素。此处数组下标表示顶点，数组元素表示该下标顶点对应的前驱顶点int[] prev = new int[adj.length];Arrays.fill(prev, -1);// 外层while循环用来遍历层while (queue.size() != 0) {int node = queue.poll();// 遍历该顶点所连接的其他顶点for (int i = 0; i < adj[node].size(); i++) {// 后继节点int backNode = adj[node].get(i);// 如果该顶点之前没有访问过if (!visited[backNode]) {// 以该顶点为数组下标保存该顶点的前驱顶点，相当于prev[]数组的每个元素保存的都是该元素的前驱顶点prev[backNode] = node;if (backNode == t) {// 递归输出路径，逆序输出，比如终点是6，则prev[6]指向的是6的前驱顶点，依次递推直到起点print(prev, s, t);return;}visited[backNode] = true;// 已经访问过的顶点加到队列中queue.add(backNode);}}}}/*** 递归打印 s->t 的路径*/private void print(int[] prev, int s, int t) {if (prev[t] != -1 && t != s) {print(prev, s, prev[t]);}System.out.println(t + " ");}
visited 数组是用来记录已被访问的顶点，避免顶点被重复访问。如果顶点 q 被访问，则 visited[q] 会被设为 true。
queue 是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，只有第 k 层的顶点都访问完才能访问第 k+1 层的顶点。当我们访问第 k 层的顶点时，我们需要把第 k 层的顶点记录下来，这样稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。
prev 数组用来记录搜索路径，但这个路径是反向存储的。prev[node] 存储的是顶点 node 是从哪个前驱顶点遍历过来的。比如我们通过顶点 2 的邻接表访问到顶点 3，那 prev[3] 就等于 2。为了正向打印出路径，我们需要递归地来打印，你可以看下 print() 函数的实现方式。
搜索过程图示：
复杂度分析：
最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。此时，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图（一个图中的所有顶点都是连通的）来说，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。
2. 深度优先搜索（DFS）
深度优先搜索（Depth-First-Search）最直观的例子就是走迷宫。当我们选择一个岔路口来走，但却发现走不通时，就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索的策略。那我们如何把这种策略应用到图中，来找某个顶点到另一个顶点的路径呢？
如下图所示。搜索的起始顶点是 s，终止顶点是 t，我们希望在图中寻找一条从顶点 s 到顶点 t 的路径。图中用深度优先搜索算法，把整个搜索的路径标记出来了。其中实线箭头表示遍历，虚线箭头表示回退。从图中可以明显看出，深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。
实际上，深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程非常适合用递归来实现。代码实现如下：
/**
* 深度优先搜索时，是否已找到终止顶点
*/
private static boolean found = false;
/**
* 深度优先搜索算法，该算法得到的路径并不是最短路径
*
* @param s 起始顶点
* @param t 终止顶点
*/
public void dfs(int s, int t) {
// 用来记录已经被访问的顶点，避免顶点被重复访问
boolean[] visited = new boolean[adj.length];
// 用来记录搜索路径，初始值都设为-1，表示没有元素。此处数组下标表示顶点，数组元素表示该下标顶点对应的前驱顶点
int[] prev = new int[adj.length];
Arrays.fill(prev, -1);
// 递归搜索路径
recurDfs(s, t, visited, prev);
// 打印路径
print(prev, s, t);
}
private void recurDfs(int node, int end, boolean[] visited, int[] prev) {
if (found) {
return;
}
visited[node] = true;
// 已找到终止顶点，退出递归
if (node == end) {
found = true;
return;
}
// 遍历该顶点连接的其他顶点
for (int i = 0; i < adj[node].size(); ++i) {
int q = adj[node].get(i);
// 如果之前已经访问过了，就跳过本次for循环，如果整个for循环结束后都没有发现新的顶点，则回到递归的上一层（回溯）
if (!visited[q]) {
prev[q] = node;
recurDfs(q, end, visited, prev);
}
}
}
我们发现，深度优先搜索代码实现也用到了 prev、visited 变量，它们跟广度优先搜索里的作用是一样的。不过，深度优先搜索代码实现里有个变量 found，它的作用是，当我们已经找到终止顶点 t 之后，我们就不再递归地继续查找了。
复杂度分析：
从图中可以看到，每条边最多会被访问两次，一次是遍历，一次是回退。所以深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。其中，visited、prev 数组的大小跟顶点的个数 V 成正比，而递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。
若有收获，就点个赞吧
0 人点赞
