Breadth first traversal of Graphs

One   The finishing touch

Breadth first traversal is also called breadth first search , Is one of the most common graph search methods . Breadth first search refers to starting from a certain point , Access all the neighboring nodes that are not accessed at one time , Then start from these visited adjacency points in turn , Access... Layer by layer . Breadth first traversal is to traverse the graph in the way of breadth first search .

In the order of breadth first search , The access sequence in the above figure is ：1 2 3 4 5 6

The secret of breadth first traversal ： First visited node , Its neighboring nodes are accessed first .

According to the breadth first traversal of the script , First come, first served , You can do this with queues . Because each node is accessed only once , So you can set an auxiliary array  visited[i] = false, It means the first one  i  Nodes not accessed ;visited[i] = true, It means the first one  i  Nodes have been accessed .

Two   Algorithm steps

1  Initialize that all nodes are accessed , And initialize an empty queue .

2  From a node in the graph  v  set out , visit  v  And mark that it has been accessed , take  v  The team .

3  If the queue is not empty , Then continue , Otherwise the algorithm ends .

4  Put the team head element  v  Out of the team , Sequential access  v  All unreachable adjacency points of , The tag has been accessed and queued , Turn to step 3.

3、 ... and   The illustration

A directed graph is shown in the following figure , The breadth first traversal process is as follows .

1  Initialization all nodes are not accessed ,visited[i] = false,i =[1,6]. And initialize an empty queue  Q.

2  From the node 1  set out , Mark that it has been accessed ,visited[1] = true, The nodes 1  The team .

3  Put the team head element 1  Out of the team , Sequential access 1  All unreachable adjacency points of 2 and 3, Mark it as visited and queued .

4  For team header element 2 Out of the team , take 2 Unreachable adjacency points 4 Mark as accessed , And put it on the team .

5  Put the team head element 3 Out of the team ,3 The adjacency point 2 Has been interviewed , No need to deal with it , The adjacency points that are not accessed 5 Mark as accessed , And put it on the team .

6   Put the team head element 4 Out of the team ,4 The adjacency point 3 Has been interviewed , No need to deal with it , The adjacency points that are not accessed 6 Mark as accessed , And put it on the team .

7  Put the team head element 5 Out of the team ,5  Adjacent node of 4 and 6 Has been interviewed , No need to deal with it , There are no adjacent points that are not accessed .

8  Put the team head element 6 Out of the team ,6 No adjacency point .

9  The queue is empty , The algorithm ends . The breadth first traversal sequence is 1 2 3 4 5 6.