迷人的兩度搜索 1、BFS和DFS 深度優先搜索演算法（DFS）和廣度優先搜索演算法（BFS）是一種用於遍歷或搜索樹或圖的演算法，在搜索遍歷的過程中保證每個節點（頂點）訪問一次且僅訪問一次，按照節點（頂點）訪問順序的不同分為深度優先和廣度優先。 1.1、深度優先搜索演算法 深度優先搜索演算法（Depth-Fi ...
迷人的兩度搜索
1、BFS和DFS
深度優先搜索演算法（DFS）和廣度優先搜索演算法（BFS）是一種用於遍歷或搜索樹或圖的演算法，在搜索遍歷的過程中保證每個節點（頂點）訪問一次且僅訪問一次，按照節點（頂點）訪問順序的不同分為深度優先和廣度優先。
1.1、深度優先搜索演算法
深度優先搜索演算法（Depth-First-Search，DFS）沿著樹的深度遍歷樹的節點，儘可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被髮現的節點，則選擇其中一個作為源節點並重覆以上過程，整個進程反覆進行直到所有節點都被訪問為止。屬於盲目搜索。
註意：
1：實際上，回溯演算法思想就是藉助於深度優先搜索來實現的。
DFS負責搜索所有的路徑，回溯輔以選擇和撤銷選擇這種思想尋找可能的解，當然代碼寫起來基於遞歸（所以代碼寫起來就是用遞歸實現的）。
2：DFS跟回溯有什麼關係呢？
回溯是一種通用的演算法，把問題分步解決，在每一步都試驗所有的可能，當發現已經找到一種方式或者目前這種方式不可能是結果的時候，退回上一步繼續嘗試其他可能（有一個選擇和撤銷選擇的過程，可理解為標記訪問和刪除訪問標記）。很多時候每一步的處理都是一致的，這時候用遞歸來實現就很自然。
當回溯(遞歸)用於樹(圖)的時候，就是深度優先搜索。當然了，幾乎所有可以用回溯解決的問題都可以表示為樹。（像之前的排列，組合等問題，雖不是直接在樹上操作，但是他們操作的中間狀態其實是一棵樹）那麼這倆在這裡就幾乎同義了。如果一個問題解決的時候顯式地使用了樹或圖，那麼我們就叫它dfs。很多時候沒有用樹我們也管它叫dfs嚴格地說是不對的，但是dfs比回溯打字的時候好輸入。
DFS代碼參考模板：
//Java
private void dfs(TreeNode root,int level,List<List<Integer>> results){
//terminal 已下探到最底部節點
if(results.size()==level){ // or root == null or node alread visited
results.add(new ArrayList<>());
return；
}
// process current level node here.
results.get(level).add(root.val); // 記錄當前節點已被訪問
//drill down if node not visited
if(root.left!=null){
dfs(root.left,level+1,results);
}
if(root.right!=null){
dfs(root.right,level+1,results);
}
}
是不是覺得跟二叉樹的前中後序遍歷很像，其實二叉樹的前中後序遍歷就是一種DFS，只不過記錄節點的時機不一樣而已。
針對多叉樹的DFS，代碼參考模板如下：
//Java
public void dfs(Node node,List<Integer> res) {
//terminal
if (node == null) {
return;
}
//process current level logic
res.add(node.val);
//drill down
List<Node> children = node.children;
for (Node n:children) {
// if node not visited then dfs node
if (not visited) { // 在基於圖的dfs中一般需要判斷頂點是否已訪問過
dfs(n,res);
}
}
}
當然我們也可以自己使用棧來模擬遞歸的過程，將遞歸代碼改寫成非遞歸代碼！
針對圖的深度優先搜索演算法，思路是一致的：
假設：從S開始進行查找，每次查找，先一頭扎到底，然後再回退，回退過程中有別的路再一頭扎到底。比如：S->A->D->G->E->B，到底了，然後回退到G，再一頭扎到底，S->A->D->G->F->C
1.2、廣度優先搜索演算法
廣度優先搜索演算法（Breadth-First-Search，BFS）直觀地講，它其實就是一種“地毯式”層層推進的搜索策略，即先查找離起始頂點最近的，然後是次近的，依次往外搜索。
簡單的說，BFS是從根節點開始，沿著樹(圖)的寬度遍歷樹(圖)的節點。如果所有節點均被訪問，則演算法中止,一般用隊列數據結構來輔助實現BFS演算法。
就像在湖面上滴一滴水，形成的水波紋！向四周散開
dfs和bfs搜索方式的比較：
BFS代碼的參考模板：需要藉助一個隊列Queue（或Deque）
//Java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> allResults = new ArrayList<>();
if (root == null) {
return allResults;
}
Queue<TreeNode> nodes = new LinkedList<>();
//將根節點入隊列
nodes.add(root);
while (!nodes.isEmpty()) {
//每次迴圈開始時：隊列中的元素的個數其實就是當前這一層節點的個數
int size = nodes.size();
List<Integer> results = new ArrayList<>();
for (int i = 0; i < size; i++) {
//從隊列中取出每一個節點（取出這一層的每個節點）
TreeNode node = nodes.poll();
results.add(node.val);
//將該節點的左右子節點入隊列
if (node.left != null) {
nodes.add(node.left);
}
if (node.right != null) {
nodes.add(node.right);
}
}
allResults.add(results);
}
return allResults;
}
就相當於剛開始把公司老總放入隊列，這是第一層，然後把老總的直接下級比如：vp，總監等，取出來，然後放入隊列，到了vp，總監這一層時，再把他們的直接下屬放入隊列。
在圖中的廣度優先搜索過程如下：
參考該網址上的演示過程：https://visualgo.net/zh/dfsbfs
應用特點：
1：BFS適合在樹或圖中求解最近，最短等相關問題
2：DFS適合在樹或圖中求解最遠，最深等相關問題
3：實際應用中基於圖的應用居多
2、面試實戰
102. 二叉樹的層序遍歷
典型的BFS，藉助隊列FIFO特性，
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
//特殊判斷
if (root == null) {
return new ArrayList();
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
List<List<Integer>> res = new ArrayList();
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList();
for (int i=0;i<size;i++) {
TreeNode poll = queue.poll();
list.add(poll.val);
//將左右子樹節點加入隊列
if (poll.left != null) {
queue.offer(poll.left);
}
if (poll.right != null) {
queue.offer(poll.right);
}
}
res.add(list);
}
return res;
}
}
時間複雜度O(n)，空間複雜度O(n)
進階：能否基於DFS完成
思路：按照深度優先遍歷，遍歷過程中將當前節點的值添加到它所對應的深度的集合中。因此需要一個在dfs過程中代表深度的變數
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList();
dfs(root,0,res);
return res;
}
public void dfs(TreeNode root,int level,List<List<Integer>> res) {
//terminal
if (root==null) {
return;
}
//將當前層的集合初始化好
int size = res.size();
if ( level > size-1) {
res.add(new ArrayList());
}
//將當前節點加到當前層對應的集合中
List<Integer> list = res.get(level);
list.add(root.val);
//drill down
dfs(root.left,level+1,res);
dfs(root.right,level+1,res);
}
}
104. 二叉樹的最大深度
如果我們知道了左子樹和右子樹的最大深度 l 和 r，那麼該二叉樹的最大深度即為
max(l,r)+1
而左子樹和右子樹的最大深度又可以以同樣的方式進行計算。因此使用遞歸
其實這也是DFS的體現，直接下探到最深處得到最大深度，然後左右兩邊比較即可。
class Solution {
public int maxDepth(TreeNode root) {
return dfs(root);
}
//求一棵子樹的最大深度
public int dfs(TreeNode node) {
//終止條件
if (node == null) {
return 0;
}
//左子樹最大深度
int leftDepth = dfs(node.left);
//右子樹最大深度
int rightDepth = dfs(node.right);
//當前節點的最大深度為左子樹最大深度和右子樹最大深度中的最大值+1
return Math.max(leftDepth,rightDepth) +1;
}
}
時間複雜度：O(n)，其中 n 為二叉樹節點的個數。每個節點在遞歸中只被遍歷一次。
空間複雜度：O(height)，其中height 表示二叉樹的高度。遞歸函數需要棧空間，而棧空間取決於遞歸的深度，因此空間複雜度等價於二叉樹的高度。
進階：能否用BFS完成
利用一個計數器，每遍歷完一層就計一個數，直到所有層都遍歷結束
class Solution {
public int maxDepth(TreeNode root) {
//特殊判斷
if (root==null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
int deep = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i=0;i<size;i++) {
TreeNode p = queue.poll();
if (p.left!=null) {
queue.offer(p.left);
}
if (p.right!=null) {
queue.offer(p.right);
}
}
//每一層節點遍歷完成後計數器+1
deep++;
}
return deep;
}
}
小結：
在實際應用中，DFS要比BFS應用的廣泛！
515. 在每個樹行中找最大值
facebook，百度，位元組面試題，515. 在每個樹行中找最大值
典型的BFS
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList();
if (root==null) {
return res;
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
int max = Integer.MIN_VALUE;
for (int i=0;i<size;i++) {
TreeNode p = queue.poll();
if (p.left !=null) {
queue.offer(p.left);
}
if (p.right!=null) {
queue.offer(p.right);
}
//比較判斷每一層的最大值
max = Math.max(max,p.val);
}
//保存每一層的最大值
res.add(max);
}
return res;
}
}
200. 島嶼數量
典型的圖的搜索，立馬想到DFS和BFS
class Solution {
//定義頂點向：上下左右，各走一步的方向信息
int[][] directions = {{0,1},{0,-1},{-1,0},{1,0}};
//定義網格的行數
int rows;
//定義網格的列數
int clos;
public int numIslands(char[][] grid) {
//定義島嶼總數
int count = 0;
//獲取網格有多少行
rows = grid.length;
if (rows==0) {
return count;
}
//獲取網格有多少列
clos = grid[0].length;
//定義網格各頂點是否被訪問過
boolean[][] visited = new boolean[rows][clos];
//從圖中去找能構成島嶼的頂點
for (int i=0;i<rows;i++) {
for (int j=0;j<clos;j++) {
//如果是陸地，並且沒有被訪問過則深度優先搜索(i,j)頂點相連的陸地。
if (grid[i][j] == '1' && !visited[i][j]) {
dfs(i,j,visited,grid);
//找到一塊count+1
count++;
}
}
}
return count;
}
//搜索與(x,y)相連的陸地頂點，並標記這些頂點。
public void dfs(int x,int y,boolean[][] visited,char[][] grid) {
//走過的頂點要標記
visited[x][y] = true;
//從該頂點，向上下左右四個方向去走
for (int i=0;i< 4;i++) {
int newX = x + directions[i][0]; // directions[i]分別代表上下左右四個方向 directions[i][0]是X軸坐標要走的距離
int newY = y + directions[i][1];
//如果新頂點在網格內,且是陸地，且沒有訪問過,則繼續搜索下去
if (inGrid(newX,newY) && grid[newX][newY]=='1' && !visited[newX][newY]) {
dfs(newX,newY,visited,grid);
}
}
}
//檢查頂點(x,y)是否在網格內
public boolean inGrid(int x,int y) {
return x>=0 && x< rows && y>=0 && y<clos;
}
}
其他題目
本文由
傳智教育博學谷教研團隊發佈。如果本文對您有幫助，歡迎
關註和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力。轉載請註明出處！
