Skip to main content

Breadth-first Search

Breadth-first Search (BFS) is one of the well-known brute-force search algorithms which has been widely used. The basic idea is just like its name: do the searching by expansion. Staring with the sources, the expansion diffuses layer by layer. In contrast, another common search algorithm is Depth-first Search (DFS) which focuses on one route first until reaching the end, then starts the next possible route.

So one way to understand BFS is that: BFS searches all the possible routes at the same time. And for each route, BFS usually makes the same amount of progress. In the middle of the search, once a route becomes invalid, it can be dropped right away.

So for BFS,

1. the minimum distance can be obtained since the shortest routes can be always found before other routes;

2. to avoid redundant search, need to make sure each position (state) is only searched once. [DFS also needs this].

3. a queue is usually used for the search, to easier realize the layer-by-layer expansion.


Example

Easy Level

Medium Level

Hard Level

Interview Questions


Upper Layer

Comments

Post a Comment

Popular posts from this blog

Dynamic Programming - Easy Level - Question 1

Dynamic Programming - Easy Level - Question 1 Leetcode 1646  Get Maximum in Generated Array You are given an integer n. An array nums of length n + 1 is generated in the following way: nums[0] = 0 nums[1] = 1 nums[2 * i] = nums[i] when 2 <= 2 * i <= n nums[2 * i + 1] = nums[i] + nums[i + 1] when 2 <= 2 * i + 1 <= n Return the maximum integer in the array nums​​​. Constraints: 0 <= n <= 100 Analysis: This question is quick straightforward: the state and transitional formula are given; the initialization is also given. So we can just ready the code to iterate all the states and find the maximum. See the code below: class Solution { public: int getMaximumGenerated(int n) { int res = 0; if(n<2) return n; vector<int> f(n+1, 0); f[1] = 1; for(int i=2; i<=n; ++i) { if(i&1) f[i] = f[i/2] + f[i/2+1]; else f[i] = f[i/2]; // cout<<i<<" "<<f[i]<<endl; ...
Post a Comment
Read more

Bit Manipulation - Medium Level

 Leetcode 416 Partition Equal Subset Sum Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal. Constraints: 1 <= nums.length <= 200 1 <= nums[i] <= 100 Analysis: There are different ways to solve this problem, such as dp with a time complexity of O(N^2). Since N is small to this question, so it is Okay to pass OJ. Besides the small N, the value of each element is also very small. So this gives us some chance to use "space to trad off time". The data structure to be used is bitset. For bitset, each bit can be either 0 or 1. The index of that bit can be used as the corresponding sum. When the bit is 1, means there is a sum with the value of its index. When a new number comes, this number needs to be added to all the previous sums, to form new "previous" sums. Thus for each number, we need to go through all the previous sums, the time co...
Post a Comment
Read more