<p id="2Q6LDQOI"><strong>摘要：</strong><br/></p><p id="2Q6LDQOJ">1，深度优先搜索介绍</p><p id="2Q6LDQOK">2，深度优先搜索的递归实现</p><p id="2Q6LDQOL">3，深度优先搜索的栈实现</p><p id="2Q6LDQOM">4，深度优先搜索与回溯算法</p><p id="2Q6LDQOO"><strong>1，深度优先搜索介绍</strong></p><p id="2Q6LDQOP">深度优先搜索(Depth-First-Search，DFS)是一种用于遍历或搜索树，图，矩阵的搜索算法，他的实现原理是：</p><p id="2Q6LDQOQ">沿着一个方向一直往下走，直到走不动为止，然后往回走，查看上一个位置还有没有其他分支没有走过，如果有就走上一个位置的其他分支，如果没有就继续回退 …… ，有一种不撞南墙不回头的感觉。</p><p id="2Q6LDQOS">访问的时候和广度优先搜索类似，需要使用一个数组 visited 来记录哪些顶点被访问过，防止重复访问。</p><p class="f_center"> <img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0621%2F1207eff2j00sff3z3003ld200kg00hdg00hx00f7.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p class="f_center"> <img src="https://nimg.ws.126.net/?url=http%3A%2F%2Fdingyue.ws.126.net%2F2024%2F0621%2F721e296cj00sff3z4001yd200kg00c2g00hx00ak.jpg&thumbnail=660x&quality=80&type=jpg"/><br/></p><p id="2Q6LDQP0">深度优先搜索的应用非常广泛，像图的连通分量，拓扑排序，环检测，路径搜索，二叉树遍历，图的遍历和搜索，解数独，走迷宫，N 皇后问题……，都可以使用 DFS 解决，所以掌握 DFS 遍历非常重要。</p> 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/191530.html