深度优先搜索depth-first search,dfs1、定义这是一种用于遍历或搜索树/图的算法。简单来说从起始节点开始沿着路径尽可能深/远地搜索直到到达叶子节点然后回溯到上一个节点继续探索未访问的路径。2、方法递归或栈3、举例岛屿数量代码注释有解释逻辑# 深度优先搜索 逻辑扫描整个二维网格--》如果遇到‘1’则以它为起始节点进行深度优先搜索 --》每个搜索到的‘1’变成‘0’--》进行深度优先搜索的次数岛屿数量 class Solution(object): def numIslands(self, grid): # 定义递归函数 def dfs(grid,i,j): grid[i][j]0 # 让搜索到的节点为0 mlen(grid) # 矩阵grid行 nlen(grid[0]) # 列 for x,y in [(i-1,j),(i1,j),(i,j-1),(i,j1)]: # 搜索起始节点的上下左右四个节点 if x0 and xm and y0 and yn and grid[x][y]1: # 保证搜索的范围不超过矩阵的大小 dfs(grid,x,y) # 递归回到这个函数定义的第一行 if not grid: # 异常检查 return 0 ans0 for i in range(len(grid)): for j in range(len(grid[0])): # 扫描矩阵 if grid[i][j]1: ans1 # 深度优先搜索的次数 岛屿数量 dfs(grid,i,j) return ans广度优先搜索breadth-first search,bfs1、定义从起始节点开始首先访问所有与起始节点【相邻】的节点然后【逐层】向外扩展搜索直到找到目标节点或者遍历完整个图。2、方法队列3、举例腐烂的橘子代码代码中使用了一个队列来存储腐烂橘子的坐标并在每次循环中对这个队列进行了多次出队和入队操作。class Solution(object): def orangesRotting(self, grid): rowlen(grid) collen(grid[0]) # 异常检查1如果全是空单元格或者烂橘子,返回0 checkall(element !1 for item in grid for element in item) if check : return 0 找出所有腐烂橘子的坐标--》遍历腐烂橘子的队列--》 搜索每一个腐烂橘子的上下左右橘子如果符合条件将该腐烂橘子变成2并且将搜索到的腐烂橘子坐标记录在队列中--》最后判断还剩下多少新鲜橘子--》剩下新鲜橘子返回0没剩下新鲜橘子返回time queue[] for i in range(row): for j in range(col): if grid[i][j]2: queue.append((i,j)) time-1 # 注意初始化时间应该是-1而不是0 while queue: current_lenlen(queue) # 在此处定义queue长度的变量而不直接在range中使用是因为下面的小循环中queue的长度可能有变化为了防止循环出错所以定义变量。 for _ in range(current_len): i,jqueue.pop(0) # 处理一个腐烂橘子就从queue踢掉这个坐标下次不再处理这个坐标 for x,y in [(1,0),(-1,0),(0,1),(0,-1)]: # 固定写法上下左右搜索 temp_iix temp_jjy if temp_i0 and temp_irow and temp_j0 and temp_j col: # 坐标必须在矩阵grid内 grid[temp_i][temp_j]2 queue.append((temp_i,temp_j)) # 搜索到新的腐烂橘子坐标就加入queue time 1 #遍历一个腐烂橘子时间加1 for item in grid: if 1 in item: # 异常检查2如果全部搜索玩还剩下新鲜橘子那么就返回-1 return -1 return time # 否则返回遍历的时间BFS与DFS的区别总的来说区别不是很大但有些细节要注意区分。1、搜索顺序不同2、搜索策略不同dfs需要设置适当的终止条件不然可能会陷入无限循环或长路径bfs可以保证找到的路径是最短路径。3、适用场景不太相同dfs适合解决图的遍历问题比如判断图是否连通、解决路径规划等问题bfs解决图的最短路径问题、状态转移图的搜索问题迷宫问题、八数码问题等。有向图-拓扑排序算法A.有向图常见概念顶点Vertex有向图中的基本单位表示图中的节点或元素。通常用不同的符号或标签来表示各个顶点。边Edge连接两个顶点的有向边具有方向性表示从一个顶点到另一个顶点的有向关系。有向边通常用箭头来表示方向。入度和出度In-degree and Out-degree对于有向图中的每个顶点其入度表示指向该顶点的边的数量出度表示从该顶点指出的边的数量。路径Path顶点序列构成的有向边序列表示从一个顶点到另一个顶点的一系列连续边的集合。有向环Directed Cycle在有向图中如果存在一条路径使得起点和终点相同并且路径中至少包含一条有向边那么这条路径就称为有向环。拓扑排序Topological Sorting有向图的一种排序方法它可以将图中的顶点线性排序使得对于图中的每一条有向边 (u, v)在排序中顶点 u 都出现在顶点 v 的前面。拓扑排序常用于任务调度、课程选修等问题中。强连通图Strongly Connected Graph在有向图中如果对于图中的任意两个顶点 u 和 v都存在从 u 到 v 和从 v 到 u 的路径那么这个图就是强连通图。强连通分量Strongly Connected ComponentsSCC有向图中的极大强连通子图即在子图内任意两个顶点都是强连通的强连通分量是有向图中一种重要的结构。B.拓扑排序详解拓扑排序的算法可以通过深度优先搜索DFS或广度优先搜索BFS实现。算法的基本思想是遍历图中的每个顶点并递归地将顶点标记为已访问然后将其所有邻接顶点加入到排序结果中。在实际应用中如果存在循环依赖即图中存在环则无法进行拓扑排序。拓扑排序有多种实现方法包括 Kahn 算法、DFS 算法等。其中 Kahn 算法是一种基于入度顶点的入边数量的贪心算法它通过不断删除入度为 0 的顶点并更新其邻接顶点的入度来实现拓扑排序。C.举例leetcode207‘课程表’关于这道题官方解析207. 课程表 Course Schedule 【LeetCode 力扣官方题解】_哔哩哔哩_bilibili做的动画非常清晰易懂总而言之就是根据入度数逐个判断。需要补充collections的一些用法知识。代码class Solution(object): def canFinish(self, numCourses, prerequisites): edgescollections.defaultdict(list) # 存储顶点信息 indeg[0]*numCourses # 创建入度数列表 res0 # 已修完的课程数 for info in prerequisites: edges[info[1]].append(info[0]) # 更新修课程顺序信息比如修完0可以修12修完1可以修3 e.g. {0:[1,2],1:[3]} indeg[info[0]] 1 # 更新入度数列表 qcollections.deque([u for u in range(numCourses) if indeg[u]0]) #创建入度数0的双端队列 while q: # 首先修完入度数0的课程因为这些课程不需要提前修其他的课程 uq.popleft() # 修完一门就从q中移除下次不做处理 res 1 for v in edges[u]: # 检索该课程修完之后可以修的课程有哪些 indeg[v]-1 # 然后把相应的课程入度数-1 if indeg[v]0: # 如果-1之后入度数0那么将该课程放入q中下次处理 q.append(v) return resnumCourses # 如果拓扑排序之后顶点数课程数代表True否则返回False前缀树Trie1、定义顾名思义trie就是每个样本都从头节点开始根据字符或前缀数字建出来的一棵大树。没有路了就新建节点有路就复用节点。每个节点只存储pass和end两种信息字符信息只在‘路’上传递。2、优点、缺点和实现方法1优点根据前缀信息来选择树上的信息可以节省大量时间。常见于搜索引擎的自动补全、word里面的拼写检查等。2缺点比较浪费空间查询时和字符数量和种类有关。3实现方法类描述静态数组推荐。内心os: 概念不难懂但是代码有点点绕如果想未来能手撕建议多打打代码熟悉下知道前缀树到底是如何实现它说的那些规则的虽然网上说静态方法更适合比赛和笔试但是你要是想搞透这个知识点两种方法都敲敲3、举例leetcode208代码class Trie(object): 模板背吧 def __init__(self): 初始化你的前缀树结构子节点树枝 self.childdict() self.iswordFalse def insert(self, word): rtself ##########相当于c的this指针 for w in word: if w not in rt.child: # 没有就新建 rt.child[w]Trie() rtrt.child[w] # 往树的下面走 rt.iswordTrue def search(self, word): rtself for w in word: if w not in rt.child: # 有字母不在这条path上断了 return False rtrt.child[w] #沿着path往下走 return rt.iswordTrue #看isword位 def startsWith(self, prefix): rtself for w in prefix: if w not in rt.child: #path断了 return False rtrt.child[w]