住房和建设部官方网站,网站建设网站建设哪里有,小程序企业网站,中小企业建站系统小朋友们好#xff0c;大朋友们好#xff01;
我是猫妹#xff0c;一名爱上Python编程的小学生。
和猫妹学Python#xff0c;一起趣味学编程。
今日主题
咱们书接上回#xff0c;上次学了图的基本概念#xff0c;你都学会了吗#xff1f;
咱们今天要学习内容如下大朋友们好
我是猫妹一名爱上Python编程的小学生。
和猫妹学Python一起趣味学编程。
今日主题
咱们书接上回上次学了图的基本概念你都学会了吗
咱们今天要学习内容如下
图的遍历算法
深度优先遍历算法dfs
这些很基础也很常用哦
图的遍历算法
计算机中图的遍历是指从图中的任一顶点出发对图中的所有顶点访问一次且只访问一次。
比如从某个顶点如何遍历图中所有的顶点 深度优先遍历算法dfs
深度优先遍历Depth-First SearchDFS是一种用于遍历或搜索图或树的算法。
它的基本思想是从图中的某个顶点开始沿着一条路径一直走到不能再走为止然后回溯到前一个顶点继续走另一条路径直到遍历完整个图或树。
在计算机中图的深度优先遍历算法通常使用递归实现。 具体步骤如下 选定一个起始顶点并将其标记为已访问。 从该顶点开始依次访问其所有未被访问过的相邻顶点。如果某个相邻顶点未被访问过则递归地对它进行深度优先遍历。 如果当前相邻顶点已被访问过则停止递归并回溯到前一个顶点。 重复步骤2和3直到所有与起始顶点相连的顶点都被访问过。
递归实现深度优先遍历算法dfs
以上图为例 12行dfs为遍历深度优先函数名称和参数其中的G表示要遍历的图v表示遍历起始顶点visited表示已经访问过的顶点。
13行已经访问过的顶点打印下。
14行将访问过的顶点存放到集合中。
15行~17行依次访问v的邻接顶点如果该顶点没有被访问过则访问它。 迭代实现深度优先遍历算法dfs
以上图为例 这里用到了列表的pop方法和extend(iterable)方法实现栈的回溯法。
pop(index) 或 pop()
弹出并返回所指定索引的元素。
传入参数索引值 index可不传。
返回指定索引的元素未指定索引则返回末尾元素 extend(iterable)将一个可迭代对象的所有元素添加到列表末尾。
传入参数可迭代对象 iterable。
返回None。
12行如果列表非空
13行创建一个集合存放已访问过顶点
14行起始顶点
16行将顶点从列表中弹出如果未访问访问
19行添加到访问集合
20行将其邻接顶点添加到列表中循环逐一访问 你学会了吗 好了我们今天就学到这里吧
如果遇到什么问题咱们多多交流共同解决。
我是猫妹咱们下次见
