BFS & DFS Note

BFS

Common Question

1. Bipartite (https://code.laioffer.com/ui/#/app/problem/56)
2. Determine whether a binary tree is a complete binary tree (https://code.laioffer.com/ui/#/app/problem/47)

DFS

Recursion VS DFS(Search Algorithm)

High level

DFS, in more general scope, it is one kind of search algorithm.

DFS can be implemented in an either recursive way or in iterative way

DFS 基本方法

• what does it store on each level? (每层代表什么意义？一般来讲解题之前就知道DFS要recurse多少层)
• How many different states should we try to put on this level? (每层有多少状态 case要try？) Eg：Print all subnets of a set S = {a, b, c}

DFS VS BFS

For some problem, DFS can be more efficient than BFS, or BFS can be more efficient than DFS.

Good Question

• Permutations (https://leetcode.com/problems/permutations/description/). You can use SWAP method to get all permutations.