DFS Summary

  1. 什么时候使用 DFS ?
  2. 组合搜索问题
  3. 递归三要素:

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)

请多多指教。

文章标题:DFS Summary

本文作者:顺强

发布时间:2019-09-18, 23:59:00

原始链接:http://shunqiang.ml/leetcode-dfs-summary/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏