定义
图（Graph）：是用于表示物体与物体之间存在某种关系的结构。数学抽象后的“物体”称作 节点 ** 或 顶点（Vertex，node或point），节点间的相关关系则称作边**(edge)，如下图：
这种关系类似人群圈子，人就是图的顶点，有关系就连接。比如维修的好友关系。分类：有向图，无向图，带权无向图等。
数据结构
可以有两种方式来存储图的结构：
- 邻接矩阵（Adjacency Matrix）：二维数组，如果2个节点i,j有边，就存储1(
a[i][j]=1)- 缺点 ：实际情况每个顶点的边并不多，那邻接矩阵的存储方法就更加浪费空间。
- 优点 ：邻接矩阵的存储方式简单、 直接，因为基于数组，所以在获取两个顶点的关系时，就非常高效。其次，用邻接矩阵存储图的另外一个好处是方便计算。这是因为，用邻接矩阵的方式存储图，可以将很多图的运算转换成矩阵之间的运算。
- 邻接表（Adjacency List）: 每个节点维护一个跟他有关系的List。
- 优点：邻接矩阵存储起来比较浪费空 间，但是使用起来比较节省时间。相反，邻接表存储起来比较节省空间，但是使用起来就比 较耗时间。
- 缺点：在邻接表中查询两个顶点之间的关系就没那么高效，将邻接表中的链表改成平衡二叉查找树解决搜索效率。
java实现如下：
import java.util.*;
public class UndirectedGraph {
private int V; // 图的顶点数
private LinkedList<Integer>[] adj; // 邻接表
// 构造函数，初始化图
public UndirectedGraph(int V) {
this.V = V;
adj = new LinkedList[V];
for (int i = 0; i < V; i++) {
adj[i] = new LinkedList<Integer>();
}
}
// 添加边
public void addEdge(int v, int w) {
adj[v].add(w);
adj[w].add(v);
}
// 获取图的顶点数
public int getV() {
return V;
}
// 获取指定顶点的邻接表
public Iterable<Integer> adj(int v) {
return adj[v];
}
}
广度优先搜索（BFS）
广度优先算法，可以回答2类问题：
- 从节点A出发，有前往节点B的路径吗？
- 从节点A出发，前往节点B的哪条路径最短？
步骤
- 维护一个队列，初始时将起点加入队列中。
- 每次从队列的头部取出一个节点，把该节点相邻的所有「未被访问过」的节点加入队列的尾部。这样，我们就可以逐层访问图中的节点。
- 不断重复步骤2。
应用场景
BFS可以用于解决很多问题，比如：
- 找到从起点到终点的最短路径（每条边的权重都为1）。
- 判断一张图是否是二分图。
- 寻找迷宫的最短路径。
示例
问题：地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
实现：
public int movingCount(int m, int n, int k) {
int[][] ints = new int[m][n];
// 1. 维护一个对列，初始时将起点加入队列中
Queue<int[]> queue= new LinkedList<>();
queue.add(new int[]{0, 0});
int count = 0;
while (!queue.isEmpty()) {
int[] node = queue.poll();
if (node[0] >= m || node[1] >= n) {
continue;
}
if (ints[node[0]][node[1]] == 1) {
continue;
}
if (getNumberSum(node[0]) + getNumberSum(node[1]) > k) {
continue;
}
// 2. 访问过，标记；
ints[node[0]][node[1]] = 1;
count++;
// 3. 把该节点相邻的所有「未被访问过」的节点加入队列的尾部
queue.add(new int[]{node[0], node[1] + 1});
queue.add(new int[]{node[0]+1, node[1]});
}
return count;
}
// 求数字各位数之和
public int getNumberSum(int number) {
int sum = 0;
while (number>0) {
sum += number % 10; // 取余得到最后一位数字
number /= 10; // 整除10，将最后一位数字删除
}
return sum;
}
复杂度分析
-
时间复杂度：O(mn)，其中
m为方格的行数，n为方格的列数。考虑所有格子都能进入，那么搜索的时候一个格子最多会被访问的次数为常数，所以时间复杂度为 O(2mn)=O(mn)。 -
空间复杂度：O(mn)，其中
m为方格的行数，n为方格的列数。搜索的时候需要一个大小为 O(mn)的标记结构用来标记每个格子是否被走过。
深度优先搜索（DFS）
深度优先搜索（Depth-First-Search）。BFS和DFS，目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式，一层层向前搜索。
举例：在朋友或朋友的朋友中找人，找找n层。
- BFS：先搜索1层关系网，再搜索二层….
- DFS: 找到一个朋友，找他的朋友，他朋友的朋友…，如果到n层没找到，再退后一层，重复搜索。
总结思想： DFS的基本思路是，从起点开始，选择一个未被访问的相邻节点，然后继续以该节点作为起点，重复上述过程。当所有相邻节点都被访问过或者已经到达目标节点时，我们回溯到上一个节点，选择另一个未被访问的相邻节点，继续访问。如果所有节点都被访问过后仍未找到目标节点，则搜索失败。
深度优先搜索用的是一种比较著名的算法思想，回溯思想。
思想示例：假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发 现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。 这种走法就是一种深度优先搜索策略。
思路
在DFS过程中，我们可以维护一个栈(或者递归)，初始时将起点加入栈中。然后，我们每次从栈顶取出一个节点，访问与该节点相邻的所有未被访问过的节点，并将它们加入栈中。
DFS可以用于解决很多问题，比如：
- 找到从起点到终点的一条路径（不一定是最短的路径）。
- 判断一张图是否是连通图。
- 计算一张图的连通分量。
问题-机器人移动
如前面的机器人移动问题，用DFS实现。
public int movingCount(int m, int n, int k) {
int[][] ints = new int[m][n];
return dfs(ints, 0, 0, k);
}
public int dfs(int[][] ints ,int i, int j, int k) {
if (i < 0 || j < 0 || i > ints.length - 1 || j > ints[0].length - 1) {
return 0;
}
if (getNumberSum(i) + getNumberSum(j) > k) {
return 0;
}
if (ints[i][j] == 1) {
return 0;
}
ints[i][j] =1;
return move(ints, i, j + 1, k)
+ move(ints, i, j - 1, k)
+ move(ints, i - 1, j, k)
+ move(ints, i + 1, j, k)
+ 1;
}
问题-括号生成
题：数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
**输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<>();
dfs("", n, n, list);
return list;
}
private void dfs(String s, int left, int right, List<String> list) {
if (left < 0 || right < 0) {
return;
}
if (left > right) {
// 右边括号大于左右，无效
return;
}
if (left == right && left == 0) {
// 括号相等，且深度最深
list.add(s);
return;
}
dfs(s + "(", --left, right, list);
++left;
dfs(s + ")", left, --right, list);
++right;
}