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