BFS：
思想：
对于图中的初始节点，先遍历初始节点的一阶邻居，当初始节点的一阶邻居都被遍历完了之后，再遍历初始节点的二阶邻居，直至所有节点都被遍历完(或找到符合条件的节点)
过程：
三要素：(1)先入先出的一个容器：队列；(2)图中的节点：最好写成单独的一个类表示；(3)已访问集合：避免重复访问。
算法过程：
(1)首先将根节点放入队列中
(2)取出队列中的第一个节点进行访问，并将其所有未被访问的邻居节点添加到队列中
(3)若队列为空则算法结束
时间复杂度：
广度优先遍历算法的时间复杂度并不确定，取决于用何种方式来表示图。
实例：
力扣第279题完全平方数，题目链接(https://leetcode-cn.com/problems/perfect-squares/)：
给定正整数 n，找到若干个完全平方数(比如 1, 4, 9, 16, …)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
分析：本题可以用动态规划的方法解，此处用广度优先遍历的方法解题
首先我们把正整数n看作是图中的初始节点，用完全平方数表示图中的边，n减去完全平方数后表示n的邻居节点。因此本题可以转换为找从n到0的最短路径。
#定义图中节点的类型，包含val和passed(经过的路径数)
class Node:
def __init__(self,val,passed = 0):
self.val = val
self.passed = passed
class Solution:
def numSquares(self, n: int) -> int:
jiedian = [Node(n)]#将初始节点放入队列
visited = [0]*n + [1]#定义节点是否被访问过，避免访问重复的节点
while jiedian:
tmp = jiedian.pop(0)#弹出首节点
#判断是否符合条件
for i in range(1,int(math.sqrt(tmp.val)+1)):
tmp_val = tmp.val – i*i
if tmp_val == 0:
return tmp.passed + 1
elif visited[tmp_val] == 0:
jiedian.append(Node(tmp_val,tmp.passed + 1))#将节点的邻居节点添加到队列
visited[tmp_val] = 1#将节点进行标记，避免重复访问
DFS：
思想：
从初始节点出发，一直沿着某条边访问下去，直至该路径上的所有节点均被访问过，再回到初始节点，从初始节点出发，沿着另一条路径开始访问，直至图中所有节点均被访问。
过程：
三要素：(1)先入先出的一个容器：栈；(2)图中的节点：最好写成单独的一个类表示；(3)已访问集合：避免重复访问。
算法过程：
(1)先将初始节点放入队列中
(2)将队列中取出第一个节点进行访问，将它某一个未被访问的节点加入队列中
(3)重复2
(4)若不存在为访问的邻居节点，将上一级节点加入到队列中，重复2
(5)直至队列为空
时间复杂度：
与BFS类似。
实例：
力扣695. 岛屿的最大面积(题目链接https://leetcode-cn.com/problems/max-area-of-island/)
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
分析：
图中每块陆地都可以当作一个节点，两个1上下左右相连视为一条边，则可以构成很多图。
#深度优先遍历搜索
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0#存储结果
for i, m in enumerate(grid):
for j, n in enumerate(m):
strack = [(i,j)]#栈
tmp = 0#记录每一块的面积
while strack:
cur_i, cur_j = strack.pop()#弹出栈尾的数据
if cur_i<0 or cur_j<0 or cur_i==len(grid) or cur_j==len(grid[0]) or grid[cur_i][cur_j] != 1:
continue
grid[cur_i][cur_j] = 0#避免重复访问
tmp += 1
for k,p in [[0,1],[0,-1],[1,0],[-1,0]]:
next_i = cur_i + k
next_j = cur_j + p
strack.append((next_i,next_j))
ans = max(ans,tmp)
return ans
其实此题还可以用广度优先遍历的方法解答：
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = 0#存储结果
for i, m in enumerate(grid):
for j, n in enumerate(m):
strack = [(i,j)]#队列
tmp = 0#记录每一块的面积
while strack:
cur_i, cur_j = strack.pop(0)#先弹出队首的数据
if cur_i<0 or cur_j<0 or cur_i==len(grid) or cur_j==len(grid[0]) or grid[cur_i][cur_j] != 1:
continue
grid[cur_i][cur_j] = 0
tmp += 1
for k,p in [[0,1],[0,-1],[1,0],[-1,0]]:
next_i = cur_i + k
next_j = cur_j + p
strack.append((next_i,next_j))
ans = max(ans,tmp)
return ans
总结：
通过上面这个题，可以看出广度优先和深度优先的区别只是遍历图中节点的顺序不同，广度优先遍历的顺序是先遍历节点的所有一阶邻居节点，然后所有二阶邻居节点。。。***可以借助队列这种数据结构实***现。深度优先遍历的是沿着一条边不停遍历下去，直至结束，才开始下一条边，可以借助栈来实现。
原文链接:https://blog.csdn.net/scp_6453/article/details/106601947