迭代加深搜索 (IDS) 或迭代加深深度优先搜索 (IDDFS)

遍历图通常有两种常见方式：BFS（广度优先搜索） 和 DFS（深度优先搜索）。如果我们面对的是一棵高度和宽度都非常巨大的树（或图），由于以下原因，这两种方式的效率都不是很理想。

• DFS（深度优先搜索） 首先会沿着根节点的一个邻接节点一直遍历下去，然后再访问下一个邻接节点。这种方法的问题是，如果一个节点离根节点很近，但不属于 DFS 最初探索的那几棵子树，那么 DFS 很晚才能到达那个节点。此外，DFS 可能无法找到到达节点的最短路径（就边的数量而言）。
• BFS（广度优先搜索） 一层一层地进行遍历，但需要更多的空间。DFS 需要的空间是 O(d)，其中 d 是树的深度；而 BFS 需要的空间是 O(n)，其中 n 是树中节点的数量（为什么呢？请注意，树的最后一层可能包含大约 n/2 个节点，倒数第二层包含 n/4 个节点，而在 BFS 中，我们需要在队列中一层接一层地存储所有节点）。

IDDFS（迭代加深深度优先搜索） 结合了深度优先搜索的空间效率和广度优先搜索的快速搜索（对于靠近根的节点）优势。
IDDFS 是如何工作的？

IDDFS 从一个初始值开始，针对不同的深度调用 DFS。在每次调用中，DFS 被限制不能超过给定的深度。所以基本上，我们是以 BFS 的方式来做 DFS。

算法：

// 如果目标节点在 max_depth 深度内可从 src 到达，
// 则返回 true
****bool**** IDDFS(src, target, max_depth)
    ****for**** limit ****from**** 0 ****to**** max_depth
       ****if**** DLS(src, target, limit) == ****true****
           ****return**** true
    ****return**** ****false****   

****bool**** DLS(src, target, limit)
    ****if**** (src == target)
        ****return**** ****true****;

    // 如果已达到最大深度，
    // 停止递归。
    ****if**** (limit <= 0)
        ****return**** ****false****;   

    ****foreach**** adjacent i of src
        ****if**** DLS(i, target, limit-1)             
            ****return**** ****true****

    ****return**** ****false****

需要注意的一点是，我们会多次访问顶层节点。最后一层（或最大深度层）被访问一次，倒数第二层被访问两次，以此类推。这可能看起来很昂贵，但实际上成本并没有那么高，因为在树中，大多数节点都位于底层。所以，即使上层被多次访问，影响也不大。下面是上述算法的实现

C++


CODEBLOCK_18aee89a


Java

`

// Java program to search if a target node is reachable from
// a source with given max depth.
import java.util.*;

// Graph class represents a directed graph using adjacency
// list representation.
class Graph {
  int V; // No. of vertices

  // Pointer to a