Breadth first search topics (BFS)

Personal home page ： A happy pig
Writing style ： Simple and clear , Just dry goods
The field of writing ： Blue bridge , Power button , Brush question skill
Support pigs ： give the thumbs-up + Collection + Focus on

BFS

1、 Search down layer by layer in hierarchical order （ But usually you don't have to search all the situations to get the answer ）
2、 Hierarchy traversal requires queue
Templates ：

void BFS(int s)
{
    
    Deque<Integer> que=new LinkedList<>();
    que.offer(s);
    while(!q.empty())
    {
    
        1、 Take out the team leader element top;
        2、 Visit the team leader element top;
        3、 Take the first element out of the team ;
        4、 take top All nodes that have not been visited in the next layer of nodes join the queue , And set it to be accessed ;
    } 
}

The second step of accessing the first element of the team can be many complex operations , Different for specific problems
The fourth step requires a visted Array to identify whether a node has been accessed

BFS There are many applications , For example, traversing a binary tree , Ergodic graph , Find the best path to the maze , There are even some abstract problems , Let's brush the questions in practice

Related topics

1、 Find in the matrix “ block “ The number of （BFS）
2、 Blue Bridge Cup 2019 Real exercise in ——4、 maze （JavaA Group ）
3、 Blue Bridge Cup 2017 The eighth real topic in - Frog jumping cup
4、 Blue Bridge Cup 2020 Real exercise in ——4、 Seven segment code （JavaA Group ）

If this article is helpful to my friends , I hope the following points can be supported ~ Thank you ！