迷人的兩度搜索
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. 二叉樹的層序遍歷
滴滴，美團點評，騰訊最近面試題，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. 二叉樹的最大深度
嘀嘀打車，百度最近面試題，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. 島嶼數量
亞馬遜，華為，位元組最近面試題，很高頻，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;
}
}
其他題目
127. 單詞接龍
529. 掃雷游戲
36. 有效的數獨
本文由
傳智教育博學谷教研團隊發布，如果本文對您有幫助，歡迎
關注和點贊；如果您有任何建議也可留言評論或私信，您的支持是我堅持創作的動力，轉載請注明出處！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/533502.html
標籤：其他
上一篇：狀態機的技術選型,yyds!