-
Notifications
You must be signed in to change notification settings - Fork 2
BFS & DFS Note
Xin Wan edited this page Apr 18, 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.
https://leetcode.com/problems/network-delay-time/description/
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.