Depth first search and breadth first search of graph traversal

This chapter will first introduce the depth first search and breadth first search of graphs , And then give C/C++/Java The implementation of the .

Catalog
1.  Graphic introduction of depth first search
1.1  Depth first search Introduction
1.2  Depth first search graph
2.  Graphic introduction of breadth first search
2.1  Introduction to breadth first search
2.2  Breadth first search diagram
3.  Search algorithm source code

Reprint please indicate the source ： If the sky doesn't die - Blog Garden

More ： Data structure and algorithm series Catalog

Graphic introduction of depth first search

1. Depth first search Introduction

Depth first search (Depth First Search), It's similar to the preorder traversal of trees .

Its ideas ： Suppose the initial state is that all the vertices in the graph are not accessed , From a certain point v set out , Access the vertex first , Then, the depth first search traversal graph starts from each of its unreached adjacency points , All the way to the sum v All vertices with paths in common are accessed . If there are other vertices of this fashion that have not been visited , Then select another vertex that is not accessed as the starting point , Repeat the process , Until all vertices in the graph are accessed .

obviously , Depth first search is a recursive process .

2. Depth first search graph

2.1 Depth first search of undirected graph

Let's say " Undirected graph " For example , To demonstrate depth first search .

For the above figure G1 Conduct depth-first traversal , From the top A Start .

The first 1 Step ： visit A.
The first 2 Step ： visit (A The adjacency point )C.
     In the 1 Step visit A after , What we should visit next is A The adjacency point , namely "C,D,F" One of them . But in the implementation of this paper , The vertices ABCDEFG Is stored in order ,C stay "D and F" In front of , therefore , First visit C.
The first 3 Step ： visit (C The adjacency point )B.
     In the 2 Step visit C after , You should visit C The adjacency point , namely "B and D" In a (A Has been visited , Not included ). And because the B stay D Before , First visit B.
The first 4 Step ： visit (C The adjacency point )D.
     In the 3 Step by step C The adjacency point B after ,B There are no adjacent points that are not accessed ; therefore , Return to visit C Another adjacent point of D.
The first 5 Step ： visit (A The adjacency point )F.
     I've already visited A, And the interview is over "A The adjacency point B All the adjacency points of ( Including recursive adjacency points )"; therefore , Return to visit A Another adjacent point of F.
The first 6 Step ： visit (F The adjacency point )G.
The first 7 Step ： visit (G The adjacency point )E.

So the order of access is ：A -> C -> B -> D -> F -> G -> E

2.2 Depth first search of digraphs

Let's say " Directed graph " For example , To demonstrate depth first search .

For the above figure G2 Conduct depth-first traversal , From the top A Start .

The first 1 Step ： visit A.
The first 2 Step ： visit B.
     During a visit to the A after , What we should visit next is A The other vertex of the edge of , Vertex B.
The first 3 Step ： visit C.
     During a visit to the B after , What we should visit next is B The other vertex of the edge of , Vertex C,E,F. In the diagram implemented in this paper , The vertices ABCDEFG Store in order , So first visit C.
The first 4 Step ： visit E.
     Next visit C The other vertex of the edge of , Vertex E.
The first 5 Step ： visit D.
     Next visit E The other vertex of the edge of , Vertex B,D. The vertices B Has been visited , So access the vertex D.
The first 6 Step ： visit F.
     Next, we should go back " visit A The other vertex of the edge of F".
The first 7 Step ： visit G.

So the order of access is ：A -> B -> C -> E -> D -> F -> G

Graphic introduction of breadth first search

1. Introduction to breadth first search

Breadth first search algorithm (Breadth First Search), Also known as " Width first search " or " Search horizontally first ", abbreviation BFS.

Its idea is ： From some vertex in the picture v set out , During a visit to the v And then access v Each of the never visited adjacency points , Then access their adjacency points one by one from each of these adjacency points , And make “ The adjacency point of the first visited vertex is accessed before the adjacency point of the later visited vertex , Until the adjacent points of all the vertices in the graph that have been accessed are accessed . If there are still vertices in the graph that are not accessed , You need to select another vertex that has not been visited as the new starting point , Repeat the process , Until all vertices in the graph are accessed .

let me put it another way , The process of breadth first searching traversal graph is based on v As a starting point , From near to far , Visit and v There are paths connected and the path length is 1,2... The summit of .

2. Breadth first search diagram

2.1 Breadth first search for undirected graphs

Let's say " Undirected graph " For example , To demonstrate breadth first search . Or take the picture above G1 Take an example to illustrate .

The first 1 Step ： visit A.
The first 2 Step ： Sequential access C,D,F.
     During a visit to the A after , Next visit A The adjacency point . I've said that before , In the implementation of this paper , The vertices ABCDEFG Stored in order ,C stay "D and F" In front of , therefore , First visit C. End of visit C after , And then visit D,F.
The first 3 Step ： Sequential access B,G.
     In the 2 End of step visit C,D,F after , Then visit their neighbors in turn . First visit C The adjacency point B, Revisit F The adjacency point G.
The first 4 Step ： visit E.
     In the 3 End of step visit B,G after , Then visit their neighbors in turn . Only G There are neighbors E, Therefore access G The adjacency point E.

So the order of access is ：A -> C -> D -> F -> B -> G -> E

2.2 Breadth first search of digraph

Let's say " Directed graph " For example , To demonstrate breadth first search . Or take the picture above G2 Take an example to illustrate .

The first 1 Step ： visit A.
The first 2 Step ： visit B.
The first 3 Step ： Sequential access C,E,F.
     During a visit to the B after , Next visit B The other vertex of the edge of , namely C,E,F. I've said that before , In the implementation of this paper , The vertices ABCDEFG Stored in order , So we will visit C, And then visit E,F.
The first 4 Step ： Sequential access D,G.
     After the interview C,E,F after , Then visit the other vertex of their edge in turn . Or in accordance with C,E,F Sequential access to ,C All have been visited , Then there's only... Left E,F; First visit E The adjacency point D, Revisit F The adjacency point G.

So the order of access is ：A -> B -> C -> E -> F -> D -> G

Search algorithm source code

Here are respectively " Adjacency matrix undirected graph "、" Adjacency table undirected graph "、" Adjacency matrix digraph "、" Adjacency table digraph " Of C/C++/Java Search algorithm source code . The source code will not be explained here ,please RTFSC; Refer to the comments in the source code .