遍歷方式中最基礎的兩種算法之 DFS - BFS

DFS(Depth first search)

Depth first search 稱作「深度優先遍歷」

下面結合具體例子來理解。如圖所示，在一個九宮格圖中，綠色位置代表起始位置，紅色代表終點位置，灰色區域和宮格圖的邊界代表此路不通，請從起始位置按照每次只能移動一格的方法移動到終點位置。

我們用 DFS 的方法去解這道題，由圖可知，我們可以走上下左右四個方向，我們不妨先約定 “左> 上 > 右 > 下” 的順序走，即，如果左邊可以走，我們先走左邊。然後「遞歸」下去，沒達到終點，我們再原路返回，等又返回到這個位置時，左邊已經走過了，那麼我們就走上面，按照這樣的順序走。並且我們把走過的路（方向）作標記表示 “不能走回頭路”。

按照約定，我們先從起點首先向左走到位置 2，這時發現左邊不能走了，這時我們就考慮往上走，發現也不能走，同理，下邊也不能走。右邊剛纔已經走過了也不能走，這時候無路可走了，代表這條路不能通往終點，所以現在「無路可走」的時候，沿着原路返回，直到回到了還有未走過的路的路口，嘗試繼續走沒有走過的路徑。

於是我們只有回到最初的位置 1，然後判斷左邊剛纔已經走過了並且證實這個方向行不通，那就不必走了，上和右也是不通，所以我們走下邊。於是走到了 6 的位置，此時還是按照約定 “左> 上>右>下” 的順序走，左邊和右邊依然不通，上邊剛纔已經走過了，所以得繼續往下走。

繼續往下那就是位置 9 了，到了這個路口我們繼續按照約定 “左> 上>右>下” 的順序，先往左發現可以走，那麼就繼續走到位置 8，到了位置 8 還是按照剛纔的思路繼續往左，發現還可以走，並且最終到達終點位置 7。

綜上所述，這個過程就是「深度優先遍歷」。

DFS 的重點在於狀態回溯，因此我們作個思路總結：

深度優先遍歷 只要前面有可以走的路，就會一直向前走，直到無路可走纔會回頭；
「無路可走」有兩種情況：① 遇到了牆；② 遇到了已經走過的路；
在「無路可走」的時候，沿着原路返回，直到回到了還有未走過的路的路口，嘗試繼續走沒有走過的路徑；
有一些路徑沒有走到，這是因爲找到了出口，程序就停止了；
「深度優先遍歷」也叫「深度優先搜索」，遍歷是行爲的描述，搜索是目的（用途）；
遍歷不是很深奧的事情，把所有可能的情況都看一遍，才能說「找到了目標元素」或者「沒找到目標元素」。遍歷也稱爲窮舉，窮舉的思想在人類看來雖然很不起眼，但藉助計算機強大的計算能力，窮舉可以幫助我們解決很多專業領域知識不能解決的問題。

使用 DFS 來解答剛纔題目的代碼如下：

//我們以紅點位置爲座標{0,0}，綠色位置座標爲{2,2}
//目標的座標位置
let target = {
  x: 0,
  y: 0
};
//綠色起點的座標位置
let currentLocation = {
  x: 2,
  y: 2
};
let used = []; //用來標記地圖上哪些點是走過的
let reached = false; //是否能到達目標位置
// 表示灰色區域的格子
const illegalLocation = [
  { x: 0, y: 2 }, //序號1的座標
  { x: 0, y: 1 }, //序號4的座標
  { x: 1, y: 1 } //序號5的座標
];

function isLegalLocation({ x, y }, illegalLocation) {
  let flag = true;
  //位置不能在地圖座標之外
  if (x < 0 || x > 2 || y < 0 || y > 2) {
    return (flag = false);
  }
  //不能走的路徑
  for (const { x: locX, y: locY } of illegalLocation) {
    if (x === locX && y === locY) {
      flag = false;
    }
  }
  return flag;
}

//向左移動
function toLeft({ x, y }) {
  return { x: x - 1, y };
}

//向上移動
function toTop({ x, y }) {
  return { x, y: y + 1 };
}

//向右移動
function toRight({ x, y }) {
  return { x: x + 1, y };
}

//向下移動
function toBottom({ x, y }) {
  return { x, y: y - 1 };
}

function dfs(target, location, illegalLocation, used) {
  // 如果當前位置與目標座標相同表示可以抵達
  if (Object.entries(target).toString() === Object.entries(location).toString()) {
    console.log('reached', location);
    return (reached = true);
  }
  let current = location;
  const newIllegalLocation = illegalLocation.concat(used);
  //假設按照“左>上>右>下”的順序走
  if (isLegalLocation(toLeft(location), newIllegalLocation)) {
    current = toLeft(location);
  } else if (isLegalLocation(toTop(location), newIllegalLocation)) {
    current = toTop(location);
  } else if (isLegalLocation(toRight(location), newIllegalLocation)) {
    current = toRight(location);
  } else if (isLegalLocation(toBottom(location), newIllegalLocation)) {
    current = toBottom(location);
  } else {
     //走不通了就直接返回
    return false
  }
  used.push(current); //將剛纔走過的格子標記爲已走過
  return dfs(target, current, illegalLocation, used); //遞歸下去
}

dfs(target, currentLocation, illegalLocation, used);
複製代碼

BFS(Breadth first search)

Breadth first search 稱作「廣度優先遍歷」

BFS 較之 DFS 之不同在於，BFS 旨在面臨一個路口時，把所有的岔路口都記下來，然後選擇其中一個進入，然後將它的分路情況記錄下來，然後再返回來進入另外一個岔路，並重復這樣的操作，用圖形來表示則是這樣的：

從綠色起點出發，記錄所有的岔路口，並標記爲走一步可以到達的。然後選擇其中一個方向走進去，我們走綠色左邊（序號爲 2）的那個格子，然後將這個路口可走的方向記錄下來並標記爲 2，意味走兩步可以到達的地方。

接下來，我們回到起點下面 1 的方塊上（序號爲 6），並將它能走的方向也記錄下來，同樣標記爲 2，因爲也是走兩步便可到達的地方。這樣走一步以及走兩步可以到達的地方都搜索完畢了，後續同理，我們可以把走三步的格子給標記出來。

再之後是第四步。我們便成功尋找到了路徑，並且把所有可行的路徑都求出來了。

注意：格子序號分別爲 1、4、5 的地方是灰色區域表示此路不通。

使用 BFS 來解答剛纔題目的代碼如下：

//我們以紅點位置爲座標{0,0}，綠色位置座標爲{2,2}
//目標的座標位置
let target = {
  x: 0,
  y: 0
};
//綠色起點的座標位置
let currentLocation = {
  x: 2,
  y: 2
};
// 表示灰色區域的格子
const illegalLocation = [
  { x: 0, y: 2 }, //序號1的座標
  { x: 0, y: 1 }, //序號4的座標
  { x: 1, y: 1 } //序號5的座標
];

function isLegalLocation({ x, y }, illegalLocation) {
  let flag = true;
  //位置不能在地圖座標之外
  if (x < 0 || x > 2 || y < 0 || y > 2) {
    return (flag = false);
  }
  //不能走的路徑
  for (const { x: locX, y: locY } of illegalLocation) {
    if (x === locX && y === locY) {
      flag = false;
    }
  }
  return flag;
}

//向左移動
function toLeft({ x, y }) {
  return { x: x - 1, y };
}

//向上移動
function toTop({ x, y }) {
  return { x, y: y + 1 };
}

//向右移動
function toRight({ x, y }) {
  return { x: x + 1, y };
}

//向下移動
function toBottom({ x, y }) {
  return { x, y: y - 1 };
}

function bfs(target, location, illegalLocation) {
  let reached = false; //是否能到達目標位置
  let stack = [];  
  let searched = new Set(); //已經走過的格子
  stack.push(location);
  while (stack.length) {
    let temp = stack.pop();
    const newIllegalLocation = illegalLocation.concat([...searched]);
    //假設按照“左>上>右>下”的順序走
    if (isLegalLocation(toLeft(temp), newIllegalLocation)) {
      temp = toLeft(temp);
    } else if (isLegalLocation(toTop(temp), newIllegalLocation)) {
      temp = toTop(temp);
    } else if (isLegalLocation(toRight(temp), newIllegalLocation)) {
      temp = toRight(temp);
    } else if (isLegalLocation(toBottom(temp), newIllegalLocation)) {
      temp = toBottom(temp);
    } else {
      //沒有通路就直接返回
      return false
    }
    searched.add(temp);
    stack.push(temp);
    for (const { x: locX, y: locY } of searched) {
      if (target.x === locX && target.y === locY) {
        //如果當前位置與目標座標相同表示可以抵達
        reached = true;
        console.log('reached: ', reached);
        stack = [];
        break;
      }
    }
  }
  return reached;
}
bfs(target, currentLocation, illegalLocation);
複製代碼

「廣度優先遍歷」的思想在生活中隨處可見：

如果我們要找一個律師，我們會先在朋友中查找，如果沒有找到，繼續在朋友的朋友中查找，直到找到爲止。
把一塊石頭投入平靜的水面，激起的一層一層波紋就呈現「廣度優先遍歷」的特點。

總結

「一條路走到底，不撞南牆不回頭」是對 DFS 的最直觀描述。因此 DFS 可以藉助「遞歸」實現。
BFS 呈現出「一層一層向外擴張」的特點，先看到的節點先遍歷，後看到的節點後遍歷，因此 BFS 可以藉助「隊列」實現。（遍歷到一個節點時，如果這個節點有左（右）孩子節點，依次將它們加入隊列。）
DFS 適合目標明確的尋找，而 BFS 適合大範圍的尋找。

關於本文

作者：Victor

https://juejin.cn/post/7185539936722878525

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/3gp-PumljeqWa1U7pj6W8Q

DFS(Depth first search)

BFS(Breadth first search)

總結

猜你喜歡