Double disk: the main differences between DFS and BFS, the differences in ideology, and the differences in code implementation

replay ：DFS And BFS The main difference , Ideological differences , Differences in code implementation

Tips ： A series of questions asked by the interviewer , I couldn't , So come down and recheck yourself , Study and summarize carefully , To cope with more possibilities in the future

About the written examination interview of Internet manufacturers , All need careful preparation
（1） Own scientific research experience , Scientific research content , Relevant field knowledge learned , Be familiar and familiar
（2） My internship experience , Did What content , Domain knowledge learned , Be familiar and familiar
（3） In addition to scientific research , Outside the internship , What I usually pay attention to Cutting edge knowledge , Don't fall , Understand carefully , The interviewer cares about whether you like to catch up with new technology , Follow up on innovative concepts and technologies
（4） Get ready Data structure and algorithm , Big factories with written examinations , The first level is to tear the code by hand to do algorithm problems
During the interview , actually , Prepare data structures and algorithms for emergencies , Have enough confidence to face the algorithm questions that the interviewer may ask , In many cases, your scientific research experience and internship experience are enough to talk to the interviewer , There is no need to test your algorithm . But many big factories will interview you and ask you algorithm questions , So no matter For the written examination interview , Data structures and algorithms must be familiar
Autumn recruit approved many big factories in advance without taking the written exam , Direct interview , Can I go to the interview without written examination , It's up to you Resume strength How strong .

---

interviewer ： Excuse me, DFS And BFS The main difference , Ideological differences , Differences in code implementation

Depth-first search （DFS）	Breadth first search （BFS）
1、DFS Search from the root node , And from the root node Maybe far away Explore these nodes .2、 Use heap Stack Data structure to remember the next node access .3、DFS The required Less memory On BFS Required memory .4、 It is controlled by LIFO （ It is the characteristic of stack ）.5、 seek Shortest distance The ideal choice for .6、 The algorithm is used to solve the problem , A topological sort , Need to backtrack the graph , Identify the loop in the graph and find the path between two nodes .	1、BFS Search from the root node , And explore all according to the tree level pattern Neighbor root .2、 It USES queue Data structure to remember the next node access .3、BFS Than DFS need More memory .4、 It uses the original application of first in first out .5、 seek Shortest path The ideal choice for .6、 This algorithm is used to find the Shortest path , Discover all the connecting components in the diagram , Whether the analysis diagram is a bipartite diagram .
BFS Traversal is neighbor by neighbor traversal ：

For example, above ,1 Neighbors of ,23 Traverse
And then look 2 Neighbors of ,45 Full traversal

however DFS, It's a road to dark , Go to a neighbor first , Then immediately go to one of the neighbors , Continue to go

Then the interviewer said ：
In fact, the biggest difference is BFS It's possible to find the shortest distance and end ,
That is to say BFS Fast , It takes up a lot of space
and DFS It's to keep walking until it's dark , Search for many shorter possibilities ,
That is to say DFS Slow speed , But save space .

It's almost enough to answer . There are not so many complicated theories .

---

summary

Tips ： Important experience ：

1） Familiar with data structure and algorithm, you can basically answer
3） Written examination AC, Space complexity can be ignored , But the interview should consider the optimal time complexity , Also consider the optimal spatial complexity .