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)

Mark visited at expansion

Time: O(|V| * |E|) Space: O(|V| * |E|)

Mark visited a generated:

Time: O(|V| + |E|) Space: O(|V|)

绑定offer和mark visited operation => guarantee each node is only offered into the queue once. => each node is only polled out of the queue once.

The graph representation of problem

You don't need to construct the whole graph representation at the very beginning. What you only need to know is:

• using what to represent the vertex. (An Integer / String ...)
• from one vertex, the function / way to get all possible neighbors.

class Vertex {
    List<Verte> nei;
}
or
Map<Integer, List<Integer>>

or 
String "abc" --> neighbor is deleting any one character. "ab", "ac", "bc"

Classical BFS Strategies

Strategy 1. About # of init and goal states

Minimum # of steps <==> shortest path from init to goal. Good question: x people with y exits, find the shortest path of any of the people to any of the exit. from the fake global init to any of the goal nodes. => Combining multiple init/goal vertex/state.

Strategy 2. BFS reconstruct shortest path

Strategy 2.1 find any one of the shortest paths

1. **Record the corresponding shortest path at each vertex when it is generated. **

store to a map<Node, shortest path>: Map<Node, List<Node>>

2. In order to remove the redundant time/space consumption? Record the previous vertex on the shortest path at each vertex.

Map<Node, Node> prevMap = new HashMap<Node, Node>();

With prevMap, you don't need visited any more. You can use prevMap to replace visited.

The path is:

List<Node> path = new ArrayList<>();
path.add(dest);
Node cur = dest;
while (cur != init) {
    cur = prevMap.get(cur);
    path.add(cur);
}
Collections.reverse(path);

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.