1. What are BFS and DFS
1.1 What is BFS
BFS (Breadth-First Search) is a graph traversal algorithm that starts from a starting point and expands the search range layer by layer until the target node is found.
This algorithm is often used to solve “shortest path” problems, such as finding the shortest path from a start point to an end point in a maze
1. First, you will start from the starting point and check all positions adjacent to it, that is, the position 1 from the starting point
2. Then, you will continue to expand outward, checking all locations that are 2 distances from the starting point, and so on until you find the exit
In BFS, you can use queues to store nodes to be searched. The starting point is first added to the queue, and then nodes are continuously taken out of the queue to check whether it is the target node. If not, all its unvisited neighbors are added to the queue. In this way, the nodes in the queue are always sorted according to their distance from the starting point, and the nodes added to the queue first are always taken out and searched first.
In this way, BFS can find the shortest path from the starting point to the target node. In practical applications, BFS can also be used to solve problems such as topological sorting and connectivity detection.
1.2 What is DFS
DFS (Depth First Search) is a graph traversal algorithm that starts from a starting point and goes down until it can go no further, then returns to the previous node and continues to explore its other branches until the target node is found. This algorithm is often used to solve “traversal” problems, such as finding all leaf nodes in a tree.
To understand DFS, you can also imagine yourself looking for all feasible paths in the maze
1. First, you will start from the starting point and follow a road until you reach a dead end.
2. Return to the previous node and continue exploring other branches
During exploration, you can use a stack to store visited nodes for later backtracking.
In DFS, you can implement depth-first search using recursion or stack. In this way, DFS can find all feasible paths, or all leaf nodes in the tree.
In practical applications, DFS can also be used to solve problems such as topological sorting and connectivity detection. Compared with BFS, DFS is generally more suitable for processing depth-first problems, while BFS is more suitable for processing breadth-first problems.
1.3 Comparison between BFS and DFS
If DFS and BFS are used to traverse all the nodes of the binary tree, the order in which they traverse the nodes is as follows:
Next, let us first look at the code comparison of BFS traversal and DFS traversal on a binary tree
The first is that DFS traversal uses recursion (the recursive method implicitly uses the system stack):
void dfs(TreeNode* root)
{
if (root == nullptr)
{
return;
}
// Recursively traverse its left subtree and right subtree in sequence
dfs(root->left);
dfs(root->right);
}
Second, BFS traversal uses the queue data structure:
void bfs(TreeNode* root)
{
//Create a queue
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
// In each loop, use q.front() to get the head node of the queue and dequeue it
TreeNode* node = q.front();
q.pop();
// Check whether the left and right child nodes of this node are empty. If not, add them to the queue.
if (node->left != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
}
}
2. Typical problems solved by applying BFS: sequential traversal
Example: Level-order traversal of a binary tree
Given a binary tree, return the node values obtained by traversing it in level order. Layer-order traversal visits all nodes layer by layer, from left to right.
What is level-order traversal? Simply put, level-order traversal is to layer the binary tree and then traverse each layer from left to right.
At first glance, this traversal order is the same as BFS, and we can directly use BFS to obtain the level-order traversal results. However, the input required by level-order traversal is different from BFS. Level-order traversal requires us to distinguish each level, which means returning a two-dimensional array. The traversal result of BFS is a one-dimensional array, and each layer cannot be distinguished.
So, how to stratify the results of BFS traversal? Let’s first observe the process of nodes entering and dequeuing during the BFS traversal:
Intercept a certain moment in the BFS traversal process:
As you can see, the nodes in the queue at this time are 3, 4, and 5, which come from layer 1 and layer 2 respectively. At this time, the nodes of the first layer have not finished coming out, and the nodes of the second layer have come in, and the nodes of the two layers are close together in the queue. We cannot distinguish which layer the nodes in the queue come from. .
Therefore, we need to slightly modify the code. Before each layer of traversal starts, first record the number of nodes in the queue (that is, the number of nodes in this layer), and then process all the nodes in this layer in one go.
//Level-order traversal of binary tree
void bfs(TreeNode* root)
{
queue<TreeNode*> q;
q.push(root);
while (!q.empty())
{
int n = q.size();
for (int i = 0; i < n; i + + )
{
TreeNode* node = q.front();
q.pop();
if (node->left != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
}
}
}
In this way, we transform BFS traversal into level-order traversal. During the traversal process, the process of nodes entering and exiting the queue is:
It can be seen that in each round of the while loop, all nodes of the current layer are dequeued, and then all nodes of the next layer are put into the queue, thus achieving layer-order traversal.
The final solution code we got is:
vector<vector<int>> levelOrder(TreeNode* root)
{
vector<vector<int>> res;
queue<TreeNode*> q;
if (root != nullptr)
{
q.push(root);
}
while (!q.empty())
{
int n = q.size();
vector<int> level;
for (int i = 0; i < n; i + + )
{
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);
if (node->left != nullptr)
{
q.push(node->left);
}
if (node->right != nullptr)
{
q.push(node->right);
}
}
res.push_back(level);
}
return res;
}
3. Typical problems solved by DFS: permutation and combination
Example: Permutation and combination
Given an array nums without duplicate numbers, return all possible permutations of it. You can return answers in any order.
Require:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]
A typical DFS template question, and one of the most representative examples of permutation and combination types, is the permutation and combination learned in high school;
Let’s talk about the specific ideas: First define several arrays, the specific meanings are as follows
vector<vector> ans; //Record the answer vector a; // record each arrangement map<int, int> book; //Whether the mark is accessed
Then loop, when nums[i] has not been accessed, add array a and mark it as having been accessed, and then perform DFS recursive operation. After the recursion ends, the accessed elements should be released and array a should be popped.
vector<vector<int>> ans; //Record the answer
vector<int> a; // record each arrangement
map<int, int> book; //Whether the mark is accessed
void DFS(int cur, int n, vector<int> & amp;nums){
if(cur==n){
ans.push_back(a);
return ;
}
for(int i= 0; i < n; i + + ){
if(book[nums[i]] == 0){
a.push_back(nums[i]);
book[nums[i]] = 1;
DFS(cur + 1, n, nums);
book[nums[i]] = 0;
a.pop_back();
}
}
}
vector<vector<int>>permute(vector<int> & nums) {
int n =nums.size();
DFS(0, n,nums);
returnans;
}
The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57512 people are learning the system