搜索分为广度优先搜索、深度优先搜索、A*算法。
一、广度优先算法（BFS）
1.1、基本实现和特性：
BFS是从一个顶点 V。开始，沿着图的宽度遍历图中的结点，如果所有结点均被访问或找到要查找的元素，则算法终止。一般用队列数据结构来辅助实现BFS算法，采用地毯式层层推进策略。
1.2、复杂度分析：
时间复杂度O（E），空间复杂度是O（V）。
1.3、步骤：
广度优先搜索使用队列来实现：
1、顶点V。放到队列的末尾
2、每次从队列的头部取出一个元素，查看这个元素的相邻结点，把它们放到队列的末尾，并把这个元素记为它的下一级元素的前驱
3、找到所要找的元素时结束程序
4、如果遍历这个图还没有找到，结束程序
1.4、应用：
1、Dijkstra单源最短路径算法
2、Prim最小生成树算法
二、深度优先搜索（DFS）
2.1、基本实现和特性：
深度优先搜索算法的思想是从一个订单V。开始，沿着一条路一直走到底，如果发现不到目标解，那就返回到上一个结点，然后从另一条路开始走到底。这种尽量往深处走的概念即是深度优先，利用的是回溯算法思想。
2.2、复杂度分析：
时间复杂度O（E），空间复杂度是O（V）
2.3、步骤：
深度优先遍历图的方法是，从图中某顶点V。出发：
1、访问顶点V。
2、依次从V。的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和V。有路径相通的顶点都被访问
3、若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。
2.4、应用：
树或者图的搜素
三、A*算法
3.1、基本概念：
A*（A-star）算法是一种静态路网中求解最短路径最有效的直接搜素方法，也是解决许多搜素问题的有效算法，算法中的距离估算值与实际值越接近，最终搜素速度越快。
四、常见面试题
例题1：200. 岛屿数量https://leetcode-cn.com/problems/number-of-islands/
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
思路：
深度优先搜索，每次搜索完，将 1 重置为 0， 1 周边（上下左右）都搜索完一圈之后，计数 + 1.
时间复杂度：O（m*n）， m为二维岛屿的长度，n为岛屿的宽度
空间复杂度：O（1）
代码实现：
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
def dfs(grid, i, j):
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]) or not grid[i][j] == '1':
return
grid[i][j] = '0'
dfs(grid, i-1, j)
dfs(grid, i, j-1)
dfs(grid, i+1, j)
dfs(grid, i, j+1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
count += 1
dfs(grid, i, j)
return count
例题2：547. 朋友圈https://leetcode-cn.com/problems/friend-circles/
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1：
输入：
[[1,1,0],
[1,1,0],
[0,0,1]]
输出：2
解释：已知学生 0 和学生 1 互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回 2 。
示例 2：
输入：
[[1,1,0],
[1,1,1],
[0,1,1]]
输出：1
解释：已知学生 0 和学生 1 互为朋友，学生 1 和学生 2 互为朋友，所以学生 0 和学生 2 也是朋友，所以他们三个在一个朋友圈，返回 1 。
思路：
深度优先搜索，dfs ， 用set集合记录访问过的元素，访问完后从1标记为0，dfs搜索完一圈之后计数+1
时间复杂度：O（n^2）
空间复杂度：O(n) ，借助set集合记录访问过的元素
代码实现：
class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
visited = set()
count = 0
def dfs(i):
for j in range(len(M)):
if j not in visited and M[i][j] == 1:
visited.add(j)
dfs(j)
# M[i][j] = 0 # 这句代码没起作用，后来我基本都删除这句代码了。
for i in range(len(M)):
if i not in visited:
dfs(i)
count += 1
return count
2021-01-09 更新记录：该题目更新啦，题号还不变，换了一个题目，解法完全一样。废话不多说，看更新后的题目。
题目：547. 省份数量 https://leetcode-cn.com/problems/number-of-provinces/
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
示例 1：
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2
示例 2：
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
思路我就不重复了，还是之前一样，直接给出参考代码，代码也还一样，换一个变量名。留一个记录，见证面试题目的换汤不换药哈~
时隔1个月还是想重复写一下思路：
题意理解：[[1,1,0],[1,1,0],[0,0,1]] 中有三个城市下标记为0,1,2. [1,1,0]表示第0个城市和第0个城市有连接，记为1， 第0个城市和第1个城市有连接，即为1，第0个城市和第2个城市没有连接，记为0，所以为 [1,1,0]，其他依次类推。
[[1,1,0],
[1,1,0],
[0,0,1]]
如果把数组写成矩阵对齐的方式，很容易一眼看出1的相连有2个方阵，左上角和右下角的单独的一个1。
单独的一个城市也算一个省份，i，j在visited中都表示自身城市和其他城市的坐标位置，ij和ji只需要访问一次，ij和ji都访问会造成统计的重复。
dfs(j) 的作用就是去重，ij和ji的关系是一样，所以只能记录一次，在dfs（i）的外面进行一次计数。
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
visited = set()
count = 0
def dfs(i):
for j in range(len(isConnected)):
if j not in visited and isConnected[i][j] == 1:
visited.add(j)
# isConnected[i][j] = 0
dfs(j)
for i in range(len(isConnected)):
if i not in visited:
visited.add(i)
count += 1
dfs(i)
return count
撰写记录
2020.12.23-06:28:00-第一次撰写
2020.12.25-07:08:00-第二次撰写
2021.01.09-09:11:10-第三次撰写
2021.02.09-09:05:00-第四次撰写
2021.02.09-22:20:00-第五次撰写
