BFS/DFS 算法在实际场景中有什么作用

Question

目前仅知道BFS/DFS 这2个算法可以用来遍历二叉树，但是他究竟能用到哪个实际场景中呢。二叉树用能用来干什么？

Answer 1

树是非线形结构，这决定了它不是一定要线性存储，这样对于大块连续内存的要求较小，有利于提高计算机资源利用率。一个例子是linux操作系统的文件系统，绝大多数都是以树的形式存储的。
下图是linux ext4文件系统的示意图：

就如上面的哥们所说，搜索文件的时候，或者在cp -r的时候，也都运用到了DFS。
和最上面的哥们有一些不同的看法，软件开发中其实在通用场景树比图的出现概率要更高一些。而DFS的用处很多时候依赖于树的功能，比如二叉搜索树DFS就是可以等价理解为O(N)排序过程。

Answer 2

不光是遍历二叉树吧，这两个算法是用来处理图的，二叉树只是一种特殊的图。我们有很多实际的结构是图或者树，比如最简单的文件目录，如果给你一个根目录，要你在里面查找符合条件的文件，你就要遍历目录结构下所有文件，这时候一般用深度优先搜索。

其他的应用也很多，比如工作流BPM，属于图结构，在上面做处理就得用bfs或者dfs。

Answer 3

比如你要启动10个服务，但是要按照一定的顺序启动，就可以把这些服务构造成有向图无环的形式，再用dfs的方式去启动，可以参考rabbitmq的启动流程。

Answer 4

举个实际例子,你有若干个项目相互依赖,编译工具就要判断是否存在循环依赖,没有的话进行偏序排序,以此来按序编译.

Answer 5

这俩在实际业务中是非常常见的算法。使用实例其实非常多，题目中所说的二叉树是一种情况，单其实不止二叉树，多叉树以及图的遍历都少不了这俩。

比如实际业务中树状结构是很常见的一种情况，比如地区信息，选定了某个县级城市，知道它的id我们想知道它上级的省份，这时候我们要找到它在树结构哪一个分支，很可能就用一个深度优先遍历一下子。

Answer 6

比如 电商网站的类目功能 理论上就是一棵树 按层次显示在页面上的时候就是二叉树的层序遍历（bfs）