递归实现深度优先搜索

    1. def DFS(cur, target, visited):
    2.     return True if cur is target
    3.     for (next : each neighbor of cur):
    4.         if next is not in visited:
    5.             add next to visited;
    6.             return true if DFS(next, target, visited) == True
    8.     return False

    不需要显示地使用栈，因为函数递归本身就是调用栈。

    递归解决方案的优点是它更容易实现。 但是，存在一个很大的缺点：如果递归的深度太高，你将遭受堆栈溢出。 在这种情况下，您可能会希望使用 BFS，或使用显式栈实现 DFS。

    1. def DFS(root, target):
    2.     visited
    3.     stack
    4.     add root to stack
    5.     while stack is not empty:
    6.         cur = the top element of stack
    7.         return true if cur is target
    8.         for (next : the neighbors of cur):
    9.             if next is not in visited:
    10.                 add next to stack;
    11.                 add next to visited;
    13.         remove cur from stack
    14.    return False

    该逻辑与递归解决方案完全相同。 但我们使用 while 循环和栈来模拟递归期间的系统调用栈。