vlambda博客
学习文章列表

    你好！我是黄果果。    

    在我们遇到问题时，有时无法寻找到题目中的规律，或者无法建立数学模型，亦或者是实现某一种算法很复杂（无法全面考虑）时，一般采用较为一般化的搜索算法。而搜索又分为深度优先搜索和广度优先搜索，今天让我们先来学习深度优先搜索（DFS : Depth-First-Search）。

    还记得大一上学期我刚刚学习程序设计基础时，老师给我们讲解了通过递归的写法计算出1到n之间的自然数，于是当时的我产生了一个疑问，我们完全可以用for循环来解决问题，而且也避免了n过大导致栈内存溢出，写起来还非常顺手，于是乎，我就把递归搁置到一边去了。直到后来的寒假，老师给我讲解了DFS之后，我才领会到了递归的妙用，也明白了递归的关键问题所在，我们首先来看下面的经典例题：

    DFS解决问题，要拆成两步来看，第一步是存图，根据题目选择恰当的数组将图封装进去。接下来第二步是搜索，利用递归的思想，一步步的进行遍历。

    其实，深度优先搜索是借助递归完成的，同时也是最相契合的。最开始学习递归的时候，大家可能觉得难在了if（）括号中应该写什么，return 后面写什么。但通过这道题我们不难发现其实递归最关键的是要寻找到出口，因为我们需要在恰当的时机逃脱掉循环。