深度优先搜索（DFS）与广度优先搜索（BFS）算法详解

深度优先搜索（DFS）与广度优先搜索（BFS）算法详解

图的遍历是图论中的基本操作，主要有两种遍历方式：深度优先遍历（DFS）和广度优先遍历（BFS）。这两种遍历方式在处理图数据时各有特点和适用场景。

广度优先遍历（BFS）

广度优先遍历也叫层序遍历，从根节点开始，依次访问每一层的所有节点。具体来说，先遍历第一层（节点 1），再遍历第二层（节点 2，3，4），然后是第三层（5，6，7，8），依此类推，直到所有节点都被访问。

在实现广度优先遍历时，需要使用队列来存储下一层待访问的节点。每次从队列中取出一个节点进行访问，并将其未访问过的邻接节点加入队列，直到队列为空。

深度优先遍历（DFS）

深度优先遍历从根节点出发，一直向左子节点走，直到左子节点不存在然后返回到上一个节点走这个节点的右子节点，然后一直往右子节点走，同样的也是走不通为止就返回。这种一路走到黑，黑了就回头的方式，就是深度优先遍历的过程。

在实现深度优先遍历时，需要使用栈来存储当前路径上的节点。每次访问一个节点时，将其未访问过的邻接节点压入栈中，然后从栈顶取出一个节点继续访问，直到栈为空。

应用场景分析

选择深度或广度所对应的是不同场景，理论上来说，所有问题，都可以用list解决，但是为什么还要分化出那么多的数据结构？还不是因为——不同的问题，采用不同的数据结构，这样解决效率才高，资源才省。

比如看这个下面这个家族结构图：

• 如果想要找到曾祖母Ruby的所有儿女，那么用广度还是广度最合适。使用广度优先搜索，那么立刻就能找到她所有直接女儿(Andrea、Xander、CoCo和Maya)，不用搜索和她相隔一代的亲人。
• 如果想要找到Ruby的一个叫Ruth的后代，用深度还是深度合适。用深度优先搜索，则可以马上移动到图的底部，在几步之内就能找到曾孙一辈。虽然还是需要遍历整幅图才能找到Ruth，但至少快速找到她是有可能的。而用广度优先搜索则别无选择，必须遍历前两辈的所有人，才能开始搜索曾孙这一辈。

在思考用深度还是广度时？应该是先思考究竟是想先尽可能在初始顶点附近搜索，还是想先尽可能远离它？

• 前者适合用广度优先搜索
• 后者适合用深度优先搜索。