-
Notifications
You must be signed in to change notification settings - Fork 2
BFS & DFS Note
Xin Wan edited this page Apr 17, 2018
·
12 revisions
- Bipartite (https://code.laioffer.com/ui/#/app/problem/56)
- Determine whether a binary tree is a complete binary tree (https://code.laioffer.com/ui/#/app/problem/47)
Time: O(|V| * |E|) Space: O(|V| * |E|)
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.
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"
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.
- **Record the corresponding shortest path at each vertex when it is generated. **
store to a map<Node, shortest path>: Map<Node, List<Node>>
- 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);
- do BFS, and record all the prev nodes (not only one) on the shortest path for each of the nodes.
- do DFS on the new graph using the "prev" relation to find all paths.
public List<List<Vertex>> findShortestPaths(Vertex init, Vertex goal) {
// handle all concer cases
// if (init == goal) return ..;
Queue<Vertex> q = new LinkedList<>();
Map<Vertex, Integer> shortestPath = new HashMap<>();
Map<Vertex, List<Vertex>> prevNodes = new HashMap<>();
shortestPath.put(init, 0);
prevNodes.put(init, new ArrayList<Vertex>());
q.offer(init);
int level = 0;
while (!q.isEmpty()) {
int size = q.size();
//q1: can we terminate at first time generate N3? No
//q2: can we terminate at expanding N3? Yes
//q3: terminate when all the shortest path level finishes for N3.
for (int i = 0; i < size; i++) {
Vertex cur = q.poll(); // cur vertex at level
for (Vertex nei : cur.neighbors) {
// if not visited
// - record #level of shortest Path, add cur to prevNodes.
// else already visited
// - if #level of cur shortest path is the same as before, add cur to prevNodes.
if (!shortestPath.contains(nei)) {
shortestPath.put(nei, level + 1);
List<Vertex> prev = new ArrayList<>();
prev.add(cur);
prevNodes.put(nei, prev);
q.offer(nei);
} else if (shortestPath.get(nei) == level + 1) {
prevNodes.get(nei).add(cur);
}
}
}
level++;
if (shortestPath.contains(goal)) {
break;
}
}
return findAllPath(prevNodes, goal, init);
}
private List<List<Vertex>> findAllPath(Map<Vertex, List<Vertex>> prevNodes, Vertex init, Vertex goal) {
List<List<Vertex>> result = new ArrayList<List<Vertex>>();
List<Vertex> curList = new ArrayList<>();
dfs(prevNodes, init, goal, curList, result);
return result;
}
private void dfs(Map<Vertex, List<Vertex>> prev, Vertex cur, Vertex goal,
List<Vertex> curList, List<List<Vertex>> result) {
//base case
if (cur == goal) {
curList.add(cur);
result.add(new ArrayList<>(curList));
curList.remove(curList.size() - 1);
return;
}
//induction rule
curList.add(cur);
for (Vertex nei : prev.get(cur)) {
dfs(prev, nei, goal, curList, result);
}
curList.remove(curList.size() - 1);
}
- try to accelerate the process of finding shortest path using BFS.
- before we find the shortest path to goal state, we still explore a lot of other nodes.
Uni-directional BFS1
- from A, do (k level) BFS1, see if we can find B
- O(n ^ k)
Bi-directional BFS1
- each round, do 1 level BFS from A and 1 level BFS from B ** check if there is any overlapped element from the explored area from A and explored area from B. *** when generate new elements from A: check if it is explored from B *** when generate new elements from B: check if it is explored from A
- until we find the first overlap - from A and B, both do n/2 levels ** if there is a shortest path from A to B, the overlapping point should be at the middle of the shortest path.
- O(2 * n^(k/2)) = O(n ^ (k / 2));
int biDirectionalBFS(Node a, Node b) {
BFSImpl bfsA = new BFSImpl(a);
BFSImpl bfsB = new BFSImpl(b);
while (bfsA.hasNodesToExplore() && bfsB.hasNodesToExplore()) {
int shortest = bfsA.nextRound(bfsB);
if (shortest != -1) } {
return shortest;
}
shortest = bfsB.nextRound(bfsA);
if (shortest != -1) {
return shortest;
}
}
return -1; // not reachable.
}
class BFSImpl {
private Queue<Node> queue;
private Map<Node, Integer> visited; // visited nodes from init and its shortest path length from int
public BFSImpl(Node init) {
queue = new ArrayDeque<Node>();
visited = new HashMap<Node, Integer>();
queue.offer(init);
visited.put(init, 0);
}
public boolean hasNodesToExplore() {
return !queue.isEmpty();
}
//generate next level
public int nextRound(BFSImpl reverse) {
int size = queue.size();
for (inti i = 0; i < size; i++) {
Node cur = queue.poll();
for (Node nei : cur.neighbors) {
// check if it is overlapped with the reverse BFS explored area.
if (reverse.visited.containsKey(nei)) {
return reverse.visited.gei(nei) + visited.get(cur) + 1;
}
// generate from A for all the neighbors
if (!visited.containsKey(nei)) {
visited.put(nei, visited.get(cur) + 1);
queue.offer(nei);
}
}
}
return -1;
}
Most basic Best First Search - Dijkstra Algorithm.
- heuristic (v to goal) is always 0
/*
candidate vertices of next min estimated cost: rv {} - some kind of data structure.
*/
initialize rv: {startVertex}
for each round: {
// what is the logic?
// 1. pick the smallest cost vertex from rv.
v = rv.pollBest();
// 2. expand v, only look at the neighbors of v. edges weight >= 0
for (neighbor n : v.neighbors) {
// generate all neighbors.
// shortest path from start, passing through v.
calculate the cost of n, v.cost + weight(v -> n)
if (n already poled out before) do nothing; // case 1
if (n not in rv) insert n to rv; // case 2
if (n already in rv and cur cost < prev cost) update n in rv; // case 3
}
}
The life cycle of a vertex
generated multiple times
|
offer/update into rv --> case2 / case3
|
expand from rv -- shortest path is determined.
|
might be generated later as well. Just ignore -- case1
Deduplication at expension
- when a vertex is already expanded, we don't need to expand it or generate it again. Deduplication at generation
- There is no deduplication at generation in classical BFS2, it is a special optimization in some particular type of graphs.
- when can we do this? ** cost will never be changed even it could be from different paths
** or later generation won't give a better estimated cost.
** reduce time / space complexity.
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}
For some problem, DFS can be more efficient than BFS, or BFS can be more efficient than DFS.
- Permutations (https://leetcode.com/problems/permutations/description/). You can use SWAP method to get all permutations.