摘要：
1，深度优先搜索介绍
2，深度优先搜索的递归实现
3，深度优先搜索的栈实现
4，深度优先搜索与回溯算法
1，深度优先搜索介绍
深度优先搜索(Depth-First-Search，DFS)是一种用于遍历或搜索树，图，矩阵的搜索算法，他的实现原理是：
沿着一个方向一直往下走，直到走不动为止，然后往回走，查看上一个位置还有没有其他分支没有走过，如果有就走上一个位置的其他分支，如果没有就继续回退 …… ，有一种不撞南墙不回头的感觉。
访问的时候和广度优先搜索类似，需要使用一个数组 visited 来记录哪些顶点被访问过，防止重复访问。
深度优先搜索的应用非常广泛，像图的连通分量，拓扑排序，环检测，路径搜索，二叉树遍历，图的遍历和搜索，解数独，走迷宫，N 皇后问题……，都可以使用 DFS 解决，所以掌握 DFS 遍历非常重要。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/58125.html