DFS Summary

DFS 会跳到根节点，结束
使用到的数据结构： 栈

什么时候使用 DFS ?

找所有方案的题目，一定是 DFS
90% DFS 的题目，要么是排列，要么是组合

组合搜索问题

问题模型：求出所有满足条件的组合
判断条件：组合中的元素是顺序无关的
时间复杂度：与 $2^n$ 相关
DFS 可以用递归实现 （Recursion）

递归三要素：

递归的定义
递归的拆解
递归的出口

dict 表示邻接矩阵
list 表示栈

def DFS(graph, s):
    stack = []
    stack = stack.append(s)
    seen = set()
    seen.add(s)
    while (len(stack) > 0):
        vertex = stack.pop()
        nodes = graph[vertex]
        for w in nodes:
            if w not in seen:
                stack.append(w)
                seen.add(w)
        print(vertex)