目录：
- 深度优先搜索
- 广度优先搜索
深度优先搜索：
深度优先搜索（Depth First Search，DFS），是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退到刚刚访问的结点。深度优先遍历是按照深度优先搜索的方式对图进行遍历。
深度优先遍历秘籍：后被访问的顶点，其邻接点先被访问。
根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。
算法步骤：
- 初始化图中所有顶点未被访问。
- 从图中的某个顶点v出发，访问v并标记已访问；
- 依次检查v的所有邻接点w，如果w未被访问，则从w出发进行深度优先遍历（递归调用，重复2—3步）。
以图1为例，进行图深度优先搜索理解：
step1：如图2，访问结点1；
step2：如图3，访问结点1的邻接点2，然后访问邻接点2的邻接点4，再访问邻接点4的邻接点5；
step3：如图4，结点5没有未访问的邻接点了，然后回退到结点4，结点4也没有未被访问的邻接点，继续回退到结点2，结点2有未被访问的邻接点6，则访问邻接点6；
step4：如图5，结点6没有未被访问的邻接点，则回退到结点2，结点也没有未被访问的邻接点，回退到结点1；
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/202614.html