快捷導(dǎo)航

JavaScript遍歷實現(xiàn)DFS算法和BFS算法

更新時間：2023年01月14日 09:33:19 作者：itwangyang

DFS(Depth?first?search)稱作「深度優(yōu)先遍歷」，BFS(Breadth?first?search)稱作「廣度優(yōu)先遍歷」。本文將通過JavaScript遍歷實現(xiàn)這兩種算法，需要的可以參考一下

DFS(Depth first search)

Depth first search 稱作「深度優(yōu)先遍歷」

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

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

按照約定，我們先從起點首先向左走到位置 2，這時發(fā)現(xiàn)左邊不能走了，這時我們就考慮往上走，發(fā)現(xiàn)也不能走，同理，下邊也不能走。右邊剛才已經(jīng)走過了也不能走，這時候無路可走了，代表這條路不能通往終點，所以現(xiàn)在「無路可走」的時候，沿著原路返回，直到回到了還有未走過的路的路口，嘗試?yán)^續(xù)走沒有走過的路徑。

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

繼續(xù)往下那就是位置 9 了，到了這個路口我們繼續(xù)按照約定“左>上>右>下” 的順序，先往左發(fā)現(xiàn)可以走，那么就繼續(xù)走到位置 8，到了位置 8 還是按照剛才的思路繼續(xù)往左，發(fā)現(xiàn)還可以走，并且最終到達終點位置 7。

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

DFS 的重點在于狀態(tài)回溯，因此我們作個思路總結(jié)：

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

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

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

function isLegalLocation({ x, y }, illegalLocation) {
  let flag = true;
  //位置不能在地圖坐標(biāo)之外
  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) {
  // 如果當(dāng)前位置與目標(biāo)坐標(biāo)相同表示可以抵達
  if (Object.entries(target).toString() === Object.entries(location).toString()) {
    console.log('reached', location);
    return (reached = true);
  }
  let current = location;
  const newIllegalLocation = illegalLocation.concat(used);
  //假設(shè)按照“左>上>右>下”的順序走
  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); //將剛才走過的格子標(biāo)記為已走過
  return dfs(target, current, illegalLocation, used); //遞歸下去
}

dfs(target, currentLocation, illegalLocation, used);

BFS(Breadth first search)

Breadth first search 稱作「廣度優(yōu)先遍歷」

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

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

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

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

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

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

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

function isLegalLocation({ x, y }, illegalLocation) {
  let flag = true;
  //位置不能在地圖坐標(biāo)之外
  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; //是否能到達目標(biāo)位置
  let stack = [];  
  let searched = new Set(); //已經(jīng)走過的格子
  stack.push(location);
  while (stack.length) {
    let temp = stack.pop();
    const newIllegalLocation = illegalLocation.concat([...searched]);
    //假設(shè)按照“左>上>右>下”的順序走
    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) {
        //如果當(dāng)前位置與目標(biāo)坐標(biāo)相同表示可以抵達
        reached = true;
        console.log('reached: ', reached);
        stack = [];
        break;
      }
    }
  }
  return reached;
}
bfs(target, currentLocation, illegalLocation);

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

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

總結(jié)

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

到此這篇關(guān)于JavaScript遍歷實現(xiàn)DFS算法和BFS算法的文章就介紹到這了,更多相關(guān)JavaScript實現(xiàn)DFS BFS內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: