深度优先（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.html
• https://cloud.tencent.com/developer/article/1156139
• https://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 < a.length; i++) {System.out.print(a[i] + "\t");}System.out.println();total++;}for (int i = 1; i <= n; i++) {if (book[i] == 0) {a[step] = i;book[i] = 1;dfs(step + 1);book[i] = 0;}}}public static void main(String[] args) {DepthFirstSearch depthFirstSearch = new DepthFirstSearch(4);depthFirstSearch.dfs(1);System.out.println("total: " + depthFirstSearch.getTotal());}public int getTotal() {return total;}
}

广度优先

public class BreadthFirstSearch {Note que[] = new Note[2501];int a[][] = new int[51][51];int book[][] = new int[51][51];//方向int next[][] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};int head, tail;int k, n, m, startX, startY, p, q, tx, ty, flag;public void init() {//起始位置startX = 1;startY = 1;//目标位置p = 9;q = 9;//地图大小n = 10;m = 10;}public void find() {//队列初始化head = 1;tail = 1;//往队列插入迷宫入口坐标que[tail] = new Note();que[tail].x = startX;que[tail].y = startY;que[tail].f = 0;que[tail].s = 0;tail++;book[startX][startY] = 1;//用来标记是否到达目标点，0表示没有达到，1表示达到flag = 0;while (head < tail) {for (k = 0; k <= 3; k++) {tx = que[head].x + next[k][0];ty = que[head].y + next[k][1];//越界判断if (tx < 1 || tx > n || ty < 1 || ty > m) {continue;}//障碍物，是否在路径中判断if (a[tx][ty] == 0 && book[tx][ty] == 0) {//已经走过book[tx][ty] = 1;//插入新的点到队列中que[tail] = new Note();que[tail].x = tx;que[tail].y = ty;que[tail].f = head;que[tail].s = que[head].s + 1;tail++;}//如果到目标点了，停止扩展，任务结束，退出循环if (tx == p && ty == q) {flag = 1;break;}}if (flag == 1) {break;}//注意这地方千万不要忘记，当一个点扩展结束后，head++才能对后面的点进行扩展head++;}}public void print() {System.out.println(que[tail - 1].s);}public static void main(String[] args) {BreadthFirstSearch breadthFirstSearch = new BreadthFirstSearch();breadthFirstSearch.init();breadthFirstSearch.find();breadthFirstSearch.print();}public static class Note {//横坐标int x;//纵坐标int y;//父亲在队列中的编号int f;//步数int s;}
}

这篇关于深度优先（DFS）和广度优先（BFS）——算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---