A, templates,

Queue<> Queue = new LinkedList<>(); Set<> visited = new Set<>(); Set<> visited = new Set<>(); Queue. Offer (start); Visited. The add (start); int step = 0;while(! queue.isEmpty()) { int size = queue.size();while(size > 0) { Node node = queue.poll(); // Check whether it is the endif(Conditions satisfied by the end point){returnstep; } // Instead of an endpoint, put the neighborhood points of this point into the queuefor(Node x: the Node to which Node is connected){if(x not invisited ){ queue.offer(x); visited.add(x); }}} // step++ is placed in this position because BFS is a layer of advance, after one layer ++ step++;Copy the code

The above is a general framework for BFS.

A, theoretical

1. Solved problems

Breadth-first search answers two types of questions: Type 1: Is there A path from node A to node B? Second question: What is the shortest path from node A to node B?

2. Implementation method

In the execution of a breadth-first search, search scope gradually extending outward from the starting point, namely first traversal search first layer near the relationship (directly connected with the target node, path length of 1), ergodic search again the second floor near relations (path length is 2), until we find the target by adding only sequential search, can be realized to check a relationship, Then check the layer 2 relationship ↑ FifO: queue implementation

At the same time, in order to avoid repeated addition of added elements and enter an infinite loop, Set, List, etc., are needed to record the added elements

3. Supplement: Theoretical knowledge of queues

A queue can only be inserted at one end and deleted at the other end. Therefore, only the earliest element that enters the queue can be deleted from the queue first. The other is the queue tail pointer, rear, which points to where the next queue element is stored

Every time you insert an element at the end of the queue, rear increases by 1; Each time an element is removed in the header, front increases by 1.

1) “underflow” phenomenon: overflow phenomenon caused by queue operation when the queue is empty. “Underflow” is a normal phenomenon and is often used as a condition for program control transfer.

(2) “true overflow” phenomenon: when the queue is full, the phenomenon of space overflow occurs when the stack operation is performed. True overflow is an error state and should be avoided.

(3) “false overflow” phenomenon: Since the head and tail Pointers only increase but not decrease in the joining and leaving operations, the space of deleted elements can never be reused. When the actual number of elements in the queue is much smaller than the size of the vector space, the queue operation may not be done because the tail pointer has exceeded the upper bound of the vector space. This phenomenon is called “false overspill”.

Whenever the rear pointer increases by 1 or the front pointer increases by 1 and exceeds the allocated queue space, let it point to the beginning of the continuous space (circular queue).

In a circular queue, there is front=rear when the queue is empty, and there is front=rear when all the queue space is full. To distinguish between the two cases, a circular queue can have at most MaxSize-1 queue elements. When there is only one empty storage unit left in the circular queue, the queue is full. So front=rear when the queue is empty, and front= (rear+1) %MaxSize when the queue is full

Queue theory section reference: blog.csdn.net/qq_37482202…