有趣的图(二)(56)

小朋友们好，大朋友们好！

我是猫妹，一名爱上Python编程的小学生。

和猫妹学Python，一起趣味学编程。

今日主题

咱们书接上回，上次学了图的基本概念，你都学会了吗？

咱们今天要学习内容如下：

图的遍历算法

深度优先遍历算法dfs

这些很基础，也很常用哦

图的遍历算法

计算机中图的遍历是指，从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。

比如，从某个顶点如何遍历图中所有的顶点？

深度优先遍历算法dfs

深度优先遍历（Depth-First Search，DFS）是一种用于遍历或搜索图或树的算法。

它的基本思想是从图中的某个顶点开始，沿着一条路径一直走到不能再走为止，然后回溯到前一个顶点，继续走另一条路径，直到遍历完整个图或树。

在计算机中，图的深度优先遍历算法通常使用递归实现。

具体步骤如下：

1. 选定一个起始顶点，并将其标记为已访问。

2. 从该顶点开始，依次访问其所有未被访问过的相邻顶点。如果某个相邻顶点未被访问过，则递归地对它进行深度优先遍历。

3. 如果当前相邻顶点已被访问过，则停止递归，并回溯到前一个顶点。

4. 重复步骤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行：将其邻接顶点添加到列表中，循环逐一访问

你学会了吗？

好了，我们今天就学到这里吧！

如果遇到什么问题，咱们多多交流，共同解决。

我是猫妹，咱们下次见！