深度优先（DFS）和广度优先（BFS） |
您所在的位置：网站首页 › 深度优先搜索的数据结构是什么意思 › 深度优先（DFS）和广度优先（BFS） |
|
深度优先
深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。----《维基百科》 广度优先广度优先搜索算法（Breadth First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。 简单的说，广度优先搜索算法是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。借助广度优先搜索算法，可以让你找出两样东西之间的最短距离。 比较 拿谚语打比方的话，深度优先搜索可以比作打破砂锅问到底、不撞南墙不回头；广度优先搜索则对应广撒网，多敛鱼两者没有绝对的优劣之分，只是适用场景不同当解决方案离树根不远或搜索深度可变时，BFS通常更好，因为只需搜索所有数据中的一部分。另外BFS的一个重要优点是它可以用于找到无权图（有权图用Dijkstra算法，贪心思想）中任意两个节点之间的最短路径（不能使用DFS）如果树比较宽而且深度有限，DFS可能是更优选项，因为DFS比BSF更节省空间，另外由于使用递归，DFS更好写（BFS必须手动维护队列） 时间复杂度都是O(n) 空间复杂度都是O(n) 参考 https://www.cnblogs.com/nkqlhqc/p/10878643.htmlhttps://cloud.tencent.com/developer/article/1156139https://zhuanlan.zhihu.com/p/125767384 java实现 深度优先 public class DepthFirstSearch { private int[] a, book; private int n; private int total; public DepthFirstSearch(int n) { a = new int[n + 1]; book = new int[n + 1]; this.n = n; total = 0; } private void dfs(int step) { if (step == n + 1) { for (int i = 1; i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |