当前位置:网站首页>Depth first traversal and breadth first traversal [easy to understand]
Depth first traversal and breadth first traversal [easy to understand]
2022-07-01 17:11:00 【Full stack programmer webmaster】
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.
.
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());
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/130947.html Link to the original text :https://javaforall.cn
边栏推荐
- Report on Market Research and investment prospects of ammonium dihydrogen phosphate industry in China (2022 Edition)
- 【C语言基础】12 字符串
- SQL question brushing 584 Looking for user references
- 剑指 Offer II 105. 岛屿的最大面积
- China sorbitol Market Forecast and investment strategy report (2022 Edition)
- 拼接字符串,得到字典序最小的结果
- 官宣!香港科技大学(广州)获批!
- 整形数组合并【JS】
- vulnhub靶场-hacksudo - Thor
- Soft test network engineer full truth simulation question (including answer and analysis)
猜你喜欢
[live broadcast appointment] database obcp certification comprehensive upgrade open class
SQL question brushing 1050 Actors and directors who have worked together at least three times
整形数组合并【JS】
C语言输入/输出流和文件操作
sql刷题584. 寻找用户推荐人
Transition technology from IPv4 to IPv6
Flux d'entrées / sorties et opérations de fichiers en langage C
【splishsplash】关于如何在GUI和json上接收/显示用户参数、MVC模式和GenParam
Pytest learning notes (13) -allure of allure Description () and @allure title()
Integer array merge [JS]
随机推荐
Yyds dry inventory MySQL RC transaction isolation level implementation
How to use etcd to realize distributed /etc directory
Report on research and investment prospects of UHMWPE industry in China (2022 Edition)
(12) About time-consuming printing
Internet News: "20220222" get together to get licenses; Many products of Jimi have been affirmed by consumers; Starbucks was fined for using expired ingredients in two stores
The amazing open source animation library is not only awesome, but also small
JDBC:深入理解PreparedStatement和Statement[通俗易懂]
Detailed explanation of string's trim() and substring()
[pyg] document summary and project experience (continuously updated
Why should you consider using prism
Oom caused by improper use of multithreading
MySQL learning summary
Research Report on development prediction and investment direction of nylon filament sewing thread in China (2022 Edition)
【C语言补充】判断明天是哪一天(明天的日期)
Judge whether the binary tree is a binary search tree
Leetcode records - sort -215, 347, 451, 75
In aks, use secret in CSI driver mount key vault
提交review时ReviewBoard出现500错误解决方法
[Supplément linguistique c] déterminer quel jour est demain (date de demain)
中国一次性卫生用品生产设备行业深度调研报告(2022版)