当前位置:网站首页>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
边栏推荐
- (十七)DAC转换实验
- 《中国智慧环保产业发展监测与投资前景研究报告(2022版)》
- PHP实现敏感词过滤系统「建议收藏」
- 走进微信小程序
- [live broadcast appointment] database obcp certification comprehensive upgrade open class
- Research and investment strategy report of neutral protease industry in China (2022 Edition)
- (十六)ADC转换实验
- In aks, use secret in CSI driver mount key vault
- 提交review时ReviewBoard出现500错误解决方法
- JDBC:深入理解PreparedStatement和Statement[通俗易懂]
猜你喜欢
LeetCode中等题之TinyURL 的加密与解密
[mathematical modeling] [matlab] implementation of two-dimensional rectangular packing code
String类
DNS
Encryption and decryption of tinyurl in leetcode
[pyg] document summary and project experience (continuously updated
SQL注入漏洞(Mysql与MSSQL特性)
String的trim()和substring()详解
Hi Fun Summer, play SQL planner with starrocks!
Leetcode records - sort -215, 347, 451, 75
随机推荐
National Security Agency (NSA) "sour Fox" vulnerability attack weapon platform technical analysis report
redis -- 数据类型及操作
反射型XSS漏洞
SystemVerilog structure (II)
(1) CNN network structure
[live broadcast appointment] database obcp certification comprehensive upgrade open class
pyqt5中,在控件上画柱状图
Hi Fun Summer, play SQL planner with starrocks!
走进微信小程序
Redis distributed lock
中国超高分子量聚乙烯产业调研与投资前景报告(2022版)
中国乙腈市场预测与战略咨询研究报告(2022版)
中国PBAT树脂市场预测及战略研究报告(2022版)
[Supplément linguistique c] déterminer quel jour est demain (date de demain)
FRP intranet penetration, reverse proxy
AI高考志愿填报:大厂神仙打架,考生付费围观
字节跳动数据平台技术揭秘:基于 ClickHouse 的复杂查询实现与优化
Basic usage of Frida
C language input / output stream and file operation
Cookies and session keeping technology