图图的存储、BFS、DFS（听说叠词很可爱）
1. 基本概念
图的基本概念中我们需要掌握的有这么几个概念：无向图、有向图、带权图；顶点（vertex）；边（edge）；度（degree）、出度、入度。下面我们就从无向图开始讲解这几个概念。
如图所示是一个无向图，图中的元素（A、B、C、D、E、F）被称为顶点（vertex），顶点可以与任意顶点建立连接关系，这种关系叫做边（edge），无向图中边是没有方向的。顶点相连接的边的条数就被称为度（degree），图中顶点 A 的度就是 3 。
还有一种图，图中的边是有方向的，如图所示，则将这种图称为有向图。度这种概念在有向图中又被扩展为入度和出度。顶点的入度是指有多少条边指向这个顶点；顶点的出度指有多少条边以这个顶点为起点。
上述的边都没有权重，假如我们要拿一个图来存储地图数据的话，图中的边还需要表示距离，那么这个图就变成了带权图（weighted graph）。在带权图中，每条边都有一个权重，这个权重可以表示距离。
★综上来看的，图的类型主要是根据边的类型来决定的。 ”
2. 图的存储
图的基本概念不多，那么在计算机中我们该如何存储图这种数据结构呢？主要有两种方式来存储图，一种是邻接矩阵的方法，另一种是邻接表的方式。
2.1. 邻接矩阵
邻接矩阵是图最直观的一种存储方式，底层依赖于二维数组。
- 对于无向图来说，如果顶点 i 和顶点 j 之间有边那么则将
A[i][j]和A[j][i]标记为 1 - 对于有向图来说，如果顶点 i 有一条边指向顶点 j，但是顶点 j 没有一条边指向顶点 i，那么则将
A[i][j]标记为 1，但是A[j][i]不用标记为 1。 - 对于带权图来说，只是从存储 1 变成存储具体的权重。
- 邻接矩阵的缺点是在表示一个图时通常很浪费存储空间。
对于无向图来说，它是一个对称矩阵，即
A[i][j]等于 1 的话，那么A[j][i]也等于 1。那么实际上只要存储一半就可以了。 另外，假如存储的是稀疏图，也就是顶点很多，但是每个顶点的边不多的一种图。那么使用邻接矩阵存储将更浪费存储空间，因为很多位置的值都是 0，这些 0 其实都是没有用的。 - 邻接矩阵的优点就是存储方式简单、直观，而且获取两个顶点的关系时非常高效。另外，使用邻接矩阵时，在计算上也很方便。因为很多图的运算实际上可以转换为矩阵的运算，比如求最短路径问题时会提到一个 Floyd-Warshall 算法，这个算法会利用到矩阵循环相乘若干次的结果。
2.2. 邻接表
图的另一种存储方法，是使用邻接表（Adjacency List）。如图所示，有向图中的每个顶点对应一个链表，该链表中存储的是该顶点指向的顶点。对于无向图来说是类似的，每个节点对应的链表中存储的是该节点所相连的顶点。
- 邻接表相比邻接矩阵的一个优点就是节省空间，但是使用起来比较耗时间（时间换空间的设计思想）。在使用邻接矩阵判断无向图中 i 和 j 之间是否存在一条边，那么只需要判断
A[i][j]是否为 1，而在邻接表中判断无向图中 i 和 j 之间是否存在一条边，那么需要判断 i 这个顶点对应的链表中是否存在 j。而且链表的方式对于缓存来说不太友好。所以，综上来说在邻接表中查询两个顶点的关系没有邻接矩阵那么高效了。 - 但是，为了让查询变得更加高效。我们可以参考散列表中提到的那样，将链表换成平衡二叉查找树（比如红黑树），或者其他动态数据结构，比如跳表、散列表，有序动态数组（结合二分查找）等。
逆邻接表
邻接表中存储的是这个顶点指向的顶点，那么逆邻接表中存储的是指向这个顶点的顶点。比如要想查看 4 这个顶点指向了哪些节点就可以使用邻接表。但是想要查看有哪些节点指向了 4 这个顶点，那么就需要逆邻接表了。
2.3. 总结
综上来说，邻接矩阵的缺点是比较浪费空间，但是优点是查询效率高，还方便矩阵运算。邻接表的优点是节省存储空间，但是不方便查找（查找效率肯定没邻接矩阵高）。对于此，我们可以将链表替换成查询效率较高的动态数据结构，比如平衡二叉树（红黑树）、跳表、散列表等。
3. 图的搜索
图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。具体方法有很多，比如有最简单、最“暴力”的深度优先、广度优先搜索，还有 A*、IDA* 等启发式搜索算法。深度优先、广度优先搜索即可以用在有向图，也可以用在无向图上。下面的实现以无向图和邻接表的存储方式为例。
3.1. 广度优先搜索（Breath-First-Search）
广度优先搜索，简称 BFS。这种搜索方法是一层层的向外搜索，先从起点开始，然后再搜索离起点最近的顶点；之后再从离起点最近的顶点出发搜索离这些顶点最近的顶点。整个过程示意图如图所示，跟二叉树的层次遍历是一样的。
相应的代码实现，如下代码所示。from 表示起点，to 表示终点。和层次遍历一样，广度优先搜索使用了队列这种数据结构。队列主要用来存储那些已经被访问，但是相邻的顶点还没有被访问的顶点。为什么使用队列这种数据结构呢？从应用场景出发，因为广度优先搜索方法是逐层访问的。也就是先访问 k 层的顶点，访问之后再去访问 k+1 层的顶点。但是，在访问第 k 层顶点的时候需要将 k+1 层的顶点也保存下来，而且 k+1 层顶点是在第 k 层顶点之后被访问并从队列中退出，也就相当于 “后来后出”。
但是，相比层次遍历又多一些内容，主要多出的是 visited 和 paths 这两个数组，visited 数组主要是用来存储顶点是否已经被访问过了，因为图相比树更为复杂，有些顶点会有多个相邻顶点。为了避免顶点被重复访问，所以借用了一个数组。
paths 数组主要用来记录从 from 到 to 的广度搜索路径，但是每个数组元素（数组下标即顶点编号）只存储该顶点前面的那个顶点，比如 paths[3] 存储 2，则表示是先访问到 2 ，然后从 2 再访问到 3。这样的存储方式是逆向的，为了正向地输出搜索路径，可以使用递归的方式，递归的时候将输出放置到递归之后。因为只有等前面的顶点递归完成之后，再输出本顶点，才是正向的路径。
public void bfsSearch(int from, int to) {
if (this.v == 0 || from == to) {
return;
}
boolean[] visited = new boolean[this.v];
int[] paths = new int[this.v]; // 记录路径，记录该节点前面的节点是哪个
for (int i = 0; i < this.v; i++) {
visited[i] = false;
paths[i] = -1;
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(from);
visited[from] = true;
while (!queue.isEmpty()) {
int w = queue.poll();
for (Integer i : this.adj[w]) {
if (!visited[i]) {
queue.offer(i);
visited[i] = true;
paths[i] = w;
if (i == to) {
printPath(paths, to);
break;
}
}
}
}
}
★另外，需要明白的是在没有权重的图中，广度优先搜索的结果就是最短路径。这个是因为广度优先搜索的方式中，每次都是取最近的节点，那么当到达终点时，其实所需次数是最少的。 ”
时间复杂度
广度优先搜索的时间复杂度最坏是遍历整个图，那么此时每个顶点都会被遍历到，每条边也会被访问一次。那么，假设边数为 E，顶点数为 V，此时时间复杂度为 O(V+E)（针对邻接表来说）。
空间复杂度
广度优先搜索时，空间复杂度主要来自于队列、visited 数组、paths 数组。这些数组的大小最大为 V，因为空间复杂度是 O(V)。
3.2. 深度优先搜索（Depth-First-Search）
深度优先搜索，简称 DFS。怎么直观的理解呢？就是你从一个顶点出发，假如这个顶点有未被访问过的顶点则访问它，然后一个一个这么套下去。当一个顶点的相邻顶点都被访问过了，那么则退回上一个顶点，然后看一下上一个顶点是否有未被访问过的邻接顶点，有的话则访问它，然后一层一层下去。如果也都被访问过了，那么则再退。一个典型的生活中的例子就是走迷宫，先一条道走到“黑”，然后看不到出口了，上一个分叉口再换条道。
如图所示，这是在图上采用深度优先搜索之后的样子，实现表示搜索方向，虚线表示回退。
深度优先搜索采用的思想是回溯思想，这种思想比较适合使用递归。我们使用递归的方式实现一下 DFS。相比 BFS，DFS 多了一个 find 变量，这个变量用于判断是否有找到顶点的。如果在没有遍历到一个顶点的最后一个邻接顶点之前就找到了终点，那么接下去的邻接顶点就可以不用遍历了，直接返回即可。
public void dfsSearch(int from, int to) {
if (this.v == 0 || from == to) {
return;
}
boolean[] visited = new boolean[this.v];
int[] paths = new int[this.v];
for (int i = 0; i < this.v; i++) {
visited[i] = false;
paths[i] = -1;
}
visited[from] = true;
reDFSS(from, to, visited, paths);
if (this.FIND_DFS == true) {
printPath(paths, to);
}
}
public void reDFSS(int from, int to, boolean[] visited, int[] paths) {
if (from == to) {
this.FIND_DFS = true;
return;
}
for (Integer i : this.adj[from]) {
if (this.FIND_DFS) {
return;
}
if (!visited[i]) {
visited[i] = true;
paths[i] = from;
reDFSS(i, to, visited, paths);
}
}
}
除了使用递归的方式实现之外，还可以将递归的方式转化成栈和循环结合的方式。在图的遍历这小节内容，你会看到非递归的方式。
★深度优先搜索找到的并不是最短路径。 ”
时间复杂度
采用同样的方法，从顶点和边的被访问次数出发，每条边最多被两次访问（一次遍历，一次回退），每个顶点被访问一次，那么时间复杂度是 O(V+E)（针对邻接表来说）。
空间复杂度
同样的，深度优先搜索的方式的空间复杂度主要来源栈、visited 数组和 paths 数组，栈的长度不可能超过顶点的个数，因此空间复杂度还是 O(V)。
3.3. 总结
- 广度和深度相比其他高级搜索算法（比如 A*算法）更简单粗暴，没有什么优化，也被称为暴力搜索算法。这两种算法适用于图不大的情况。
- 深度优先搜索主要借助了栈的方式，这个栈可以是函数调用栈也可以是栈这种数据结构（因为递归也可以转化为非递归的方式）。广度优先搜索主要使用队列。
- 图和树的比较，图的 DFS 类似于树的先序遍历；BFS 类似于树的层次遍历。
- 在没有权重的图中，BFS 搜索的路径结果就是最短路径；DFS 搜索的结果却不一定，因为 DFS 会“绕来绕去”，而 BFS 很直接每次都是最近的。
- 在求图的时间复杂度时，常用的方法是从顶点和边被遍历的次数出发。
4. 图的遍历
与图的搜索算法有点不同的是，图的遍历是指将图中的所有点都遍历一次。常见的遍历方法有深度优先遍历和广度优先遍历。这两种遍历方法的思想还是一样的，简单来说就是图的搜索方法就是加了一个节点判断，如果找到相应的节点就停止搜索。下面直接给出相应的代码，不再赘述。
4.1. 广度优先遍历
public void bfsTraversal() {
if (this.v == 0) {
return;
}
boolean[] visited = new boolean[this.v];
for (int i = 0; i < this.v; i++) {
visited[i] = false;
}
Queue<Integer> queue = new LinkedList<>();
queue.offer(0);
visited[0] = true;
while (!queue.isEmpty()) {
int w = queue.poll();
System.out.print(w + "\t");
for (Integer i : this.adj[w]) {
if (visited[i] == false) {
queue.offer(i);
visited[i] = true;
}
}
}
}
4.2. 深度优先遍历
// 递归的方式
public void dfsTraversal() {
if (this.v == 0) {
return;
}
boolean[] visited = new boolean[this.v];
for (int i = 0; i < this.v; i++) {
visited[i] = false;
}
for (int i = 0; i < this.v; i++) {
if (!visited[i]) {
reDFST(i, visited);
}
}
}
public void reDFST(int f, boolean[] visited) {
visited[f] = true;
System.out.print(f + "\t");
for (Integer i : this.adj[f]) {
if(!visited[i]) {
reDFST(i, visited);
}
}
}
// 非递归的方式，使用了栈
public void dfsTraversalStack() {
if (this.v == 0) {
return;
}
boolean[] visited = new boolean[this.v];
for (int i = 0; i < this.v; i++) {
visited[i] = false;
}
Stack<Integer> stack = new Stack<>();
stack.push(0);
visited[0] = true;
System.out.print(0 + "\t");
while (!stack.isEmpty()) {
int w = stack.peek();
int flag = 0;
for (Integer i : this.adj[w]) {
if (!visited[i]) {
stack.push(i);
visited[i] = true;
System.out.print(i + "\t");
flag = 1;
break;
}
}
if (flag == 0) {
stack.pop();
}
}
}
巨人的肩膀
- 极客时间-《数据结构与算法》-王争老师