wordpres做影视网站,云浮网站建设公司,广州越秀区核酸检测点查询,外贸网站翻译建设课程目标
了解树/图的深度遍历#xff0c;宽度遍历基本原理#xff1b;会使用python语言编写深度遍历#xff0c;广度遍历代码#xff1b;掌握拓扑排序算法
搜索算法的意义和作用
搜索引擎
提到搜索两个子#xff0c;大家都应该会想到搜索引擎#xff0c;搜索引擎的基…课程目标
了解树/图的深度遍历宽度遍历基本原理会使用python语言编写深度遍历广度遍历代码掌握拓扑排序算法
搜索算法的意义和作用
搜索引擎
提到搜索两个子大家都应该会想到搜索引擎搜索引擎的基本工作步骤 网页爬取 — 数据预处理 — 排序 — 查询 第一步网页爬取非常重要简单来说就是给爬虫蜘蛛程序或者爬虫机器人分配一组起始的网页爬取一个网页后解析提取出这个网页里的所有超链接再依次爬取出这些超链接再提取网页超链接如此不断重复从而提取网页内容。 海量的网页链接之间最终构成了一张图于是问题就变成了如何遍历这张图。 现在的网络网站机构复杂信息太多所以蜘蛛爬行也是有一定策略的。基础就是广度优先和深度优先两种。现实确实时间和带宽优先再大的搜索引擎也仅仅只能是收入小部分网页。提升网络爬虫的主要方法有提升网站权重/频繁更新/导入链接/减短与首页的距离等等。
深度优先搜索DFS
定义与基本内容
深度优先搜索属于图算法的一种Depth First Search。其过程简要来说就是对每一个可能的分支路径深入到不能深入为止而且每一个节点只能访问一次。
深度优先搜索是每一次按照一个方向进行穷尽式的搜索当该方向上的搜索无法继续往前的时候这时候就退回到上一步换一个方向继续搜索。
算法演示如下
树的深度优先搜索
从跟节点开始一直搜索左子树直到某个节点没有左子树为止接着换个方向搜索右子树。如图 DFS的序列为先序遍历0 — 1 — 3 — 4 — 2 — 5 — 6
无向图的深度优先搜索
假设初始状态是图中所有顶点均未被访问则从某个顶点v出发首先访问该顶点然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到则另选一个未被访问的顶点作起始点重复上述过程直至图中所有顶点都被访问到为止。 从顶点A开始深度优先搜索
访问A访问A的相邻节点C访问C的相邻节点B在步骤3中访问了C的邻节点B之后B周围没有邻节点未被访问因此返回C节点访问C的另一个邻节点D在步骤4中访问了D后D周围没有未被访问的邻接点因此返回C再返回A访问F访问F的邻接点G访问G的邻接点E
访问的顺序A—C—B—D—F—G—E
有向图的深度优先搜索 步骤1访问A步骤2访问A的出边的顶点B步骤3访问B的出边的顶点C步骤4访问C的出边的顶点E步骤5访问E的出边的顶点D和BB在步骤2中已经访问过了所以访问D步骤6返回之前的节点直到碰到还有未访问的出边顶点所以访问到B的出边顶点F步骤7访问G
访问顺序A—B—C—E—D—F—G
典型题目200. 岛屿数量
https://leetcode.cn/problems/number-of-islands/description/ DFS深度优先搜索问题通常在树或者图结构上进行的而这道提属于网络结构网络结构要比二叉树结构稍微复杂它其实是一个简化版的图结构。 分析
访问相邻节点网络结构中上下左右四个位置都是相邻节点。坐标为x, y的格子其四个相邻的格子分别为x-1y x1y xy-1 xy1判断base case如果走进超出网格返回的格子那么直接返回先往四个方向走一步再说如果发现走出了网格范围再赶紧返回标记已经遍历过的格子。我们只关注值为1的格子做DFS遍历每走过一个陆地格子那就把格子的值改成0.
思路
采用DFS方式从ij向此点的上下左右i1 ji-1 j i j-1i j1做深度搜索终止条件①ij越过矩阵边界②非陆地搜索岛屿的同时将遍历过的地方改为0以免重复搜索相同岛屿
主循环 遍历整个矩阵当遇到grid[i][j]1时从此点开始做深度优先搜索dfs岛屿的数量1且在深度优先搜索中删除此岛屿。 最终返回岛屿数量count。
class Solution:def numIslands(self, grid: List[List[str]]) - int:def dfs(grid, i, j, rows, cols):# 退出条件if i 0 or i rows - 1 or j 0 or j cols - 1 or grid[i][j] ! 1:returngrid[i][j] 0dfs(grid, i, j1, rows, cols)dfs(grid, i, j-1, rows, cols)dfs(grid, i1, j, rows, cols)dfs(grid, i-1, j, rows, cols)rows len(grid)if rows 0:return 0cols len(grid[0])num_islands 0for i in range(rows):for j in range(cols):# 只有确认时岛屿才会遍历if grid[i][j] 1:# 发现岛屿岛屿个数加1num_islands 1dfs(grid, i, j, rows, cols)return num_islands附录基础
python基础语法
python基础精讲 http://t.csdnimg.cn/HdKdi
本专栏主要针对python基础语法帮助学习者快速接触并掌握python大部分最重要的语法特征。 1、基本数据类型和变量 2、分支结构与循环结构 3、函数与异常处理 4、类与模块 5、文件读写
通过本专栏可以快速掌握python的基础语法。
python数据结构与算法理论基础专栏
数据结构与算法pythonhttp://t.csdnimg.cn/Gb6MN 程序 数据结构 算法而且在面试过程中这些是必考必问的内容。内容大纲基础数据结构树、链表、栈、队列等、常见算法排序算法、递归算法等。
专栏是基于python的基础知识是很好的入门学习资料。帮助大家快速理解这些数据结构和常见算法的概念同时结合力扣题目也能更好的掌握这些知识达到在面试中游刃有余的效果。
