Depth first traversal and breadth first traversal [easy to understand]

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Depth first traversal and breadth first traversal

What is? depth / Breadth Traverse first ？

Depth first traversal DFS（Depth First Search）, Breadth first traversal BFS（Breadth First Search）, They are two ways to traverse all the vertices in a graph .

What's the difference between these two traversal methods ？ Let's take a chestnut ：

We came to a playground , There's... In the playground 11 A scenic spot . We go from the scenic spots 0 Start , To visit all the attractions in the playground , What kind of play order can there be ？

The first one is to stick to the bottom . We choose a bypass , Go as far as you can , If you have a dead end, go back , If you encounter a branch that has not been explored in the process of fallback , Just go into the bypass and continue to go deep .

In the picture , First of all, we choose scenic spots 1 This road , Keep going deep into the scenic spots 7、 Scenic spot 8, Finally, I found I couldn't walk （ The numbers next to the attractions represent the order of exploration ）：

therefore , We go back to the scenic spot 7, And then explore the attractions 10, It's a dead end again . therefore , Back to the scenic spot 1, Explore scenic spots 9：

So this is the way to think about it , Let's go back to the scenic spot 0, Follow up to explore the scenic spots in turn 2、3、5、4、6, Finally, I played all over the playground ：

Go deep like this , Go back to the end and look for other ways to traverse , It's called depth first traversal （DFS）.

In addition to depth first traversal of such a head to end play , We have another way to play ： First of all, the starting point adjacent to several attractions to play through , Then go play a little farther from the starting point （ Next floor ） The sights of , And then I'll play a little further away from the starting point （ Two layers apart ） The sights of …

In the picture , We first explore the scenic spots 0 The adjacent attractions of 1、2、3、4：

next , We explore with attractions 0 Scenic spots on the next floor 7、9、5、6：

Last , We explore with attractions 0 Scenic spots two floors apart 8、10：

Such a layer by layer traversal from the inside out , It's called breadth first traversal （BFS）.

Depth-first traversal

First of all, let's talk about the implementation process of depth first traversal . What does backtracking mean here ？ Backtracking, as the name suggests , It's from back to front , Trace back to the path that has been taken .

Take the data structure of our amusement park as an example , If we visit the vertex in turn 0、1、7、8, Found no way to go , At this point, we're going to go from the apex 8 Back to the top 7.

![ Insert picture description here ](https://img-blog.csdnimg.cn/20190529211147549.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2EyMjE3MDE4MTAz,size_16,color_FFFFFF,t_70

And then we explored the apex 10, There's no way to go again , At this point, we're going to go from the apex 10 Back to the top 7, Back to the top 1.

Like this, trace back to the path you've visited from back to front , It's called backtracking .

To achieve backtracking , You can take advantage of the first in, last out feature of the stack , You can also use recursion （ Because recursion itself is based on the method call stack ）.

Let's demonstrate the implementation process .

First visit the vertex 0、1、7、8, These four vertices are put on the stack in turn , Now the vertex 8 It's the top of the stack ：

From the top 8 Back to the top 7, The vertices 8 Out of the stack ：

Next, go to the top 10, The vertices 10 Push ：

From the top 10 Back to the top 7, From the top 7 Back to the top 1, The vertices 10 And vertex 7 Out of the stack ：

Explore the apex 9, The vertices 9 Push ：

And so on , Using such a temporary stack to implement backtracking , Finally, all the vertices are traversed .

Breadth first traversal

Next, it's time to talk about the implementation of breadth first traversal . What do you mean by replay ？ It sounds like a retrospective ？ Actually , Backtracking and replay are exactly the opposite process .

Still take the picture just now as an example , According to the idea of breadth first traversal , We first traverse the vertices 0, Then it traverses the adjacent vertices 1、2、3、4：

Next we're going to traverse the outer vertices , But how to find these more peripheral vertices ？ We need to take the vertices we've just traversed 1、2、3、4 Go over it again in order , From the top 1 Find adjacent vertices 7、9; From the top 3 Find adjacent vertices 5、6.

Let's review the traversed vertices in the same order as before , It's called replay . alike , Additional storage space is needed to achieve playback , You can use the first in, first out feature of the queue to achieve .

Let's demonstrate the implementation process . First, traverse the starting vertex 0, The vertices 0 The team ：

The next summit 0 Out of the team , Traversal vertex 0 Adjacent vertices of 1、2、3、4, And put them in the team ：

And then the apex 1 Out of the team , Traversal vertex 1 Adjacent vertices of 7、9, And put them in the team ：

And then the apex 2 Out of the team , There is no new top to join the team ：

And so on , Using such a queue to replay , Finally, all the vertices are traversed .

/**

 The top of the graph 

/ private static class Vertex { int data; Vertex(int data) {    this.data = data; } } /*

 chart （ Adjacency table form ）

/ private static class Graph { private int size; private Vertex[] vertexes; private LinkedList adj[]; Graph(int size){    this.size = size;    // Initialize vertex and adjacency matrix     vertexes = new Vertex[size];    adj = new LinkedList[size];    for(int i=0; i*

 Depth-first traversal 

/ public static void dfs(Graph graph, int start, boolean[] visited) { System.out.println(graph.vertexes[start].data); visited[start] = true; for(int index : graph.adj[start]){    if(!visited[index]){        dfs(graph, index, visited);    } } } /*

 Breadth first traversal 

*/

public static void bfs(Graph graph, int start, boolean[] visited, LinkedList queue) {

queue.offer(start);

while (!queue.isEmpty()){

   int front = queue.poll();

   if(visited[front]){

       continue;

   }

   System.out.println(graph.vertexes[front].data);

   visited[front] = true;

   for(int index : graph.adj[front]){

       queue.offer(index);;

   }

}

}

public static void main(String[] args) {

Graph graph = new Graph(6);

graph.adj[0].add(1);

graph.adj[0].add(2);

graph.adj[0].add(3);

graph.adj[1].add(0);

graph.adj[1].add(3);

graph.adj[1].add(4);

graph.adj[2].add(0);

graph.adj[3].add(0);

graph.adj[3].add(1);

graph.adj[3].add(4);

graph.adj[3].add(5);

graph.adj[4].add(1);

graph.adj[4].add(3);

graph.adj[4].add(5);

graph.adj[5].add(3);

graph.adj[5].add(4);

System.out.println(" Depth first traversal of graphs ：");

dfs(graph, 0, new boolean[graph.size]);

System.out.println(" Breadth first traversal of graphs ：");

bfs(graph, 0, new boolean[graph.size], new LinkedList());

}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/130947.html Link to the original text ：https://javaforall.cn