算法修炼：深度遍历

文章预览

图的遍历一般使用深度优先搜索/广度优先搜索（DFS/BFS）算法，目前很多面试题目都可以利用这种思路来解决。 深度优先搜索是一种用于遍历或搜索树或图形数据结构的算法，该算法从根节点开始（在图形的情况下，选择一些任意节点作为根节点），并在回溯之前尽可能沿着每个分支进行探索。因此，基本思想是从根节点或任意节点开始，标记该节点，接着移至相邻的未标记节点，然后继续此循环，直到没有未标记的相邻节点为止。最后回溯并检查其他未标记的节点并遍历它们。 采用深度优先搜索解题的要点： 设置初始条件； 利用变量防止循环或者已经遍历过的节点； 确定下一个阶段需要遍历的节点。 深度优先搜索的应用 深度优先搜索（DFS）是用于遍历图形的算法（或技术）。使用DFS可以解决很多问题： 对于加权图，图的深度优先遍历将生成 ………………………………