PAGE1

PAGE1

深度优先：深度优先搜索的应用：深度优先搜索与贪心算法的结合应用

1深度优先搜索基础

1.1深度优先搜索的概念

深度优先搜索（Depth-FirstSearch，简称DFS）是一种用于遍历或搜索树或图的算法。在树中，DFS从根节点开始，尽可能深地搜索树的分支。如果到达一个节点的子节点死胡同，则回溯到父节点，并探索父节点的其他子节点。在访问完一个节点的所有可到达的子节点后，该节点被标记为已访问。DFS可以用于解决许多问题，如迷宫求解、路径寻找、连通性分析等。

1.1.1例子：使用DFS遍历二叉树

classTreeNode:

def__i