图-广度优先搜索、深度优先搜索
转自某故事会。
最近在看数据结构中图的相关知识，之前看的很混乱，现在总算是理清了，在此记录一下。
目录：
- 图的基本知识
- 广度优先搜索（BFS）
- 深度优先搜索（DFS）
- 总结
- 代码实现
一、图的基本知识
日常有很多地方都用到了图，比如地铁线路图，计算机网络连线图等。
图就就是下面这种由节点和连接每对节点的边所构成的图形。
这是最简单的图，我们可以根据图的一些特性将其进行分类：
1、如果给边加上一个值表示权重，这种图就是加权图，没有权重的图就是非加权图，没有权重的边只能表示两个节点的连接状态，而有权重的边就可以表示节点之间的“连接程度”。
2、如果给边加上表示方向的箭头，即表示节点之间的传递方向，这种图就是有向图，而边上没有箭头的图就是无向图。
3、如果图中任意两个节点都能找到路径可以将它们进行连接，则称该图为连通图，上面这个图就是连通图，反之则为非连通图。
下面两个图分别为加权图和有向图：
非连通图如下所示：
知道了什么是图，和图相关的算法主要有两类：
- 图的搜索算法：图的搜索指的就是从图的某一节点开始，通过边到达不同的节点，最终找到目标节点的过程。根据搜索的顺序不同，图的搜索算法可分为“广度优先搜索”和“深度优先搜索”两种。
- 图的最短路径问题：最短路径问题就是要在两个节点的所有路径中，找到一条所经过的边的权重总和最小的路径。相关算法有“贝尔曼-福特算法”，“狄克斯特拉算法”和“A* 算法”三种。
二、广度优先搜索
广度优先搜索和深度优先搜索一样，都是对图进行搜索的算法，都是从起点开始顺着边搜索，此时并不知道图的整体结构，直到找到指定节点(即终点)。在此过程中每走到一个节点，就会判断一次它是否为终点。
广度优先搜索会根据离起点的距离，按照从近到远的顺序对各节点进行搜索。而深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条路径。
在广度优先搜索中，有一个保存候补节点的队列，队列的性质就是先进先出，即先进入该队列的候补节点就先进行搜索。
下图中红色表示当前所在的节点（节点A），终点设为节点G，将与节点A直连的三个节点B, C, D放入存放候补节点的队列中（与节点A直连的三个节点放入时可以没有顺序，这里的放入顺序为B, C, D），用绿色表示。
此时队列中有B, C, D三个节点，我们来看看广度优先搜索是如何对各节点进行搜索的。
1、上面左图：此时从队列中选出一个节点，优先选择最早放入队列的那个节点，这里选择最左边的节点B。将已经搜索过的节点变为橙色（节点A），搜索到节点B时，将与节点B直连的两个节点E和F放入队列中，此时队列为 [C, D, E, F]。
2、上面中图：对节点B搜索完毕，节点B不是要找的终点，再搜索节点C，将与节点C直连的节点H放入队列中，此时队列为 [D, E, F, H]。
3、然后对节点D进行同样的操作，此时队列为 [E, F, H, I, J]。
4、上面右图：对与节点A直连的节点搜索完毕，再对与节点B直连的节点进行搜索（因为剩下的点中它们最先放入队列），这里选择节点E，将与节点E直连的节点K放入队列中，此时队列为 [F, H, I, J, K]。
然后一直按照这个规则进行搜索，直到到达目标节点G为止，搜索结束。
广度优先搜索为从起点开始，由近及远进行广泛的搜索。因此，目标节点离起点越近，搜索结束得就越快。
三、深度优先搜索
在深度优先搜索中，保存候补节点是栈，栈的性质就是先进后出，即最先进入该栈的候补节点就最后进行搜索。
还是将起点设为节点A，终点设为节点G，还是先将与节点A直连的三个节点B, C, D放入存放候补节点的栈中（这里的放入顺序为D, C, B）。到这里和广度优先搜索似乎没什么区别。
因为节点B是最后放入，则先从节点B开始搜索，将与节点B直连的两个节点E和F放入栈中，此时栈为 [D, C, F, E]。
接下来就可以看出深度优先搜索和广度优先搜索存在的区别了。
1、上面左图：然后再对节点E进行搜索，将与节点E直连的节点K放入栈中，此时栈为 [D, C, F, K]。
2、此时节点K在栈的最后，所以先对节点K进行搜索，节点K不是终点，而且节点K没有其他直连的节点，所以此时栈为 [D, C, F]。
3、上面中图：然后再对节点F进行搜索，节点F也不是终点，而且节点F也没有其他直连的节点，所以此时栈为 [D, C]。
3、上面右图：接下来就对节点C进行搜索，将与节点C直连的节点H放入栈中，此时栈为 [D, H]。
然后一直按照这个规则进行搜索，直到到达目标节点G为止，搜索结束。
深度优先搜索会沿着一条路径不断往下，搜索直到不能再继续为止，到了路径的尽头，再折返，再对另一条路径进行搜索。
四、总结
虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，但是在操作步骤上却只有一点不同，那就是选择哪一个候补节点作为下一个节点的基准不同。
广度优先搜索选择的是最早成为候补的节点，因为节点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的节点，所以会一路往下，沿着新发现的路径不断深入搜索。
上面介绍过连通图的定义，通过深度优先搜索可以判断图是否是连通图。具体实现为：在图中任意选择一个节点，从该节点开始进行深度优先搜索，如果在这个搜索过程中所有的节点都被搜索到，则该图为连通；反之，若存在没有被搜索到的节点，则说明该图是非连通的。
在广度优先搜索的执行过程中，搜索范围从起点开始逐渐向外延伸，所以不但可以判断两个节点之间是否有路径，还可以找出这两个节点的最短路径，即可以解决最短路径问题。
广度优先搜索可以用于找到两个节点的最短路径问题，这里的最短路径其实是针对于非加权图，寻找段数最少的路径。但是对于加权图，段数最少的路径并不代表路径中的权重总和也最小。
对于加权图，计算最短路径可以如下三个算法：
- 贝尔曼-福特算法（(Bellman-Ford）
- 狄克斯特拉算法（Dijkstra）
- A* 算法（A-Star）
五、代码实现
我们要对下面这个有向图进行广度优先搜索和深度优先搜索。
我们用字典来表示整个图，图由多个节点组成。将节点与其所有邻近节点的关系用键值对来表示，代码如下：
graph = {}
graph["A"] = ["B", "D", "F"]
graph["B"] = ["C", "E"]
graph["D"] = ["C"]
graph["F"] = ["G", "H"]
graph["C"] = []
graph["E"] = []
graph["G"] = []
graph["H"] = []键表示每个节点，值是一个数组，其中包含了键的所有邻近节点，这里的邻近节点是指从键所表示的节点出发，箭头所指向的其他节点。没有邻近节点的键所对应的值为空列表。
广度优先搜索
这里使用函数 deque 来创建一个双端列表，可以实现在列表两端添加(append)和弹出(pop)元素。
from collections import deque
search_queue = deque() # 创建一个节点列表
search_queue += graph["A"] # 表示将"A"的相邻节点都添加到节点列表中我们指定 “A” 为起点，”G” 为终点。
需要一个 searched 数组来保存搜索过的节点，防止同一个节点被多次搜索。
每次从节点列表的最左边取出节点。
完整代码如下：
from collections import deque
def search(start_node):
search_queue = deque()
search_queue += graph[start_node]
searched = [] # 这个数组用于记录检查过的节点
while search_queue: # 只要节点列表不为空
node = search_queue.popleft() # 取出节点列表中最左边的节点
print(node, end=' ') # 打印出当前节点
if not node in searched: # 如果这个节点没检查过
if node == 'G': # 检查这个节点是否为终点"G"
print("\nfind the destination!")
return True
else:
search_queue += graph[node] # 将此节点的相邻节点都添加到节点列表中
searched.append(node) # 将这个节点标记为检查过
# 如果节点列表为空仍没找到终点，则返回False
return False
print(search("A"))运行上述代码，可以得到输出：
B D F C E C G
find the destination!
True根据节点的输出顺序就可以知道搜索顺序符合广度优先搜索的规则。
深度优先搜索
只需将上面代码中的
node = search_queue.popleft() # 取出节点列表中最左边的节点改为如下语句即可。
node = search_queue.pop() # 取出节点列表中最右边的节点所以广度优先搜索和深度优先搜索的区别就只是选择哪一个候补节点作为下一个节点的基准不同。
我们指定 “A” 为起点，”B” 为终点，并运行上述代码，可以得到输出：
F H G D C B
find the destination!
True根据节点的输出顺序就可以知道搜索顺序符合深度度优先搜索的规则。
运行时间
在整个图中寻找终点，就意味着将沿每条边前行，因此运行时间至少为O(边数)。
我们还使用了一个队列，其中包含要检查的每个节点，将一个节点添加到队列需要的时间是固定的，即为O(1)，因此对每个节点都这样做需要的总时间为O(节点数)。
所以广度（深度）优先搜索的运行时间为O(节点数 + 边数)，通常写作O(V + E)，其中V为节点(vertice)数，E(edge)为边数。
代码-Java
class Solution {
// 四角 1,0 0,1 0,-1 -1,0
int[] dx = {1, 0, 0, -1};
int[] dy = {0, 1, -1, 0};
// 处理跟目标位置值一样的。这里采用修改对应位置值的方式
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length;
// 数组中值为0和1，操作时，将其改成其他值，标识处理过
int newColor = 2, maxSize = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1)
maxSize = Math.max(maxSize, bfsMethod(grid, i, j, newColor));
// maxSize = Math.max(maxSize, dfsMethod(grid, i, j, newColor));
// maxSize = Math.max(maxSize, dfsMethod1(grid, i, j, newColor, 1));
return maxSize;
}
// 深度-栈
private int dfsMethod(int[][] image, int sr, int sc, int newColor) {
// 行
var rowLen = image.length;
// 列
var rankLen = image[0].length;
// 处理的次数
var con = 0;
// 起始点颜色
var curColor = image[sr][sc];
// 定义栈
// var stack = new Stack<int[]>();
// LinkList可当栈用，使用push和pop方法
var stack = new LinkedList<int[]>();
// 先改再存
image[sr][sc] = newColor;
con++;
// 存放
stack.push(new int[]{sr, sc});
while (!stack.isEmpty()) {
// 取出
var cell = stack.pop();
int x = cell[0], y = cell[1];
// var oldColor = image[x][y];
// // 某些情况下，可能已经被改过一次了，避免重复
// if (oldColor != newColor) {
// image[x][y] = newColor;
// con++;
// }
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < rowLen && my >= 0 && my < rankLen && image[mx][my] == curColor && image[mx][my] != newColor) {
// 先改再存。而非取的时候再改，能避免重复
image[mx][my] = newColor;
con++;
stack.push(new int[]{mx, my});
}
}
}
return con;
}
// 广度-队列
private int bfsMethod(int[][] image, int sr, int sc, int newColor) {
// 行
var rowLen = image.length;
// 列
var rankLen = image[0].length;
// 处理的次数
var con = 0;
// 起始点颜色
var curColor = image[sr][sc];
// 定义队列
// LinkList可当队列用，使用offer和poll方法
var queue = new LinkedList<int[]>();
// 先改再存
image[sr][sc] = newColor;
con++;
// 存放
queue.offer(new int[]{sr, sc});
while (!queue.isEmpty()) {
// 取出
var cell = queue.poll();
int x = cell[0], y = cell[1];
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < rowLen && my >= 0 && my < rankLen && image[mx][my] == curColor && image[mx][my] != newColor){
// 先改再存。而非取的时候再改，能避免重复
image[mx][my] = newColor;
con++;
queue.offer(new int[]{mx, my});
}
}
}
return con;
}
// 深度优先算法-递归
private int dfsMethod1(int[][] image, int x, int y, int newColor, int oldColor) {
// 不超出范围
if (x < 0 || x >= image.length || y < 0 || y >= image[0].length)
return 0;
// 已染过色不做处理、且只染与原颜色相同的
var curColor = image[x][y];
if (curColor == newColor || curColor != oldColor)
return 0;
image[x][y] = newColor;
var ans = 1;
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
ans += dfsMethod1(image, mx, my, newColor, oldColor);
}
return ans;
}
//--------------------------------------------------------------------
// 广度-队列-计算层级
private int bfsRankMethod(int[][] grid, int goalVal) {
// 行
var m = grid.length;
// 列
var n = grid[0].length;
// 视业务要求
var newVal = 2;
//--------------------start---------------
// 这一块代码，当起点不值一个时，可能需要定一个名为超级源点的起始，在这里把目标起点放入队列
// 定义队列
// LinkList可当队列用，使用offer和poll方法
var queue = new LinkedList<int[]>();
// 这里视作这么目标点都是从一个源点出发的
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 将目标点放入
if (grid[i][j] == goalVal) {
// 先改再存
grid[i][j] = newVal;
// 存放
queue.offer(new int[]{i, j});
}
}
}
//-----------------------end--------------
// 处理的轮数
var con = 0;
while (!queue.isEmpty()) {
// 每次处理一层
var size = queue.size();
for (int l = 0; l < size; l++) {
// 取出
var cell = queue.poll();
int x = cell[0], y = cell[1];
for (int i = 0; i < 4; i++) {
int mx = x + dx[i], my = y + dy[i];
if (mx >= 0 && mx < m && my >= 0 && my < n && grid[mx][my] == goalVal && grid[mx][my] != newVal) {
// 先改再存。而非取的时候再改，能避免重复
grid[mx][my] = newVal;
queue.offer(new int[]{mx, my});
}
}
}
// 扩展次数。若队列中无元素，表示已无法扩展，本次不计
if (!queue.isEmpty())
con++;
}
return con;
}
}数据结构与算法可以说是计算机专业最重要的一门学科，掌握熟练不管是求职还是继续深造都是非常有用的。