JavaScript遍歷實(shí)現(xiàn)DFS算法和BFS算法
DFS(Depth first search)
Depth first search 稱作「深度優(yōu)先遍歷」
下面結(jié)合具體例子來理解。如圖所示，在一個九宮格圖中，綠色位置代表起始位置，紅色代表終點(diǎn)位置，灰色區(qū)域和宮格圖的邊界代表此路不通，請從起始位置按照每次只能移動一格的方法移動到終點(diǎn)位置。
我們用 DFS 的方法去解這道題，由圖可知，我們可以走上下左右四個方向，我們不妨先約定 “左>上>右>下” 的順序走，即，如果左邊可以走，我們先走左邊。然后「遞歸」下去，沒達(dá)到終點(diǎn)，我們再原路返回，等又返回到這個位置時，左邊已經(jīng)走過了，那么我們就走上面，按照這樣的順序走。并且我們把走過的路（方向）作標(biāo)記表示“不能走回頭路”。
按照約定，我們先從起點(diǎn)首先向左走到位置 2，這時發(fā)現(xiàn)左邊不能走了，這時我們就考慮往上走，發(fā)現(xiàn)也不能走，同理，下邊也不能走。右邊剛才已經(jīng)走過了也不能走，這時候無路可走了，代表這條路不能通往終點(diǎn)，所以現(xiàn)在「無路可走」的時候，沿著原路返回，直到回到了還有未走過的路的路口，嘗試?yán)^續(xù)走沒有走過的路徑。
于是我們只有回到最初的位置 1，然后判斷左邊剛才已經(jīng)走過了并且證實(shí)這個方向行不通，那就不必走了，上和右也是不通，所以我們走下邊。于是走到了 6 的位置，此時還是按照約定“左>上>右>下” 的順序走，左邊和右邊依然不通，上邊剛才已經(jīng)走過了，所以得繼續(xù)往下走。
繼續(xù)往下那就是位置 9 了，到了這個路口我們繼續(xù)按照約定“左>上>右>下” 的順序，先往左發(fā)現(xiàn)可以走，那么就繼續(xù)走到位置 8，到了位置 8 還是按照剛才的思路繼續(xù)往左，發(fā)現(xiàn)還可以走，并且最終到達(dá)終點(diǎn)位置 7。
綜上所述，這個過程就是「深度優(yōu)先遍歷」。
DFS 的重點(diǎn)在于狀態(tài)回溯，因此我們作個思路總結(jié)：
- 深度優(yōu)先遍歷 只要前面有可以走的路，就會一直向前走，直到無路可走才會回頭；
- 「無路可走」有兩種情況：① 遇到了墻；② 遇到了已經(jīng)走過的路；
- 在「無路可走」的時候，沿著原路返回，直到回到了還有未走過的路的路口，嘗試?yán)^續(xù)走沒有走過的路徑；
- 有一些路徑?jīng)]有走到，這是因?yàn)檎业搅顺隹?，程序就停止了?/li>
- 「深度優(yōu)先遍歷」也叫「深度優(yōu)先搜索」，遍歷是行為的描述，搜索是目的（用途）；
- 遍歷不是很深奧的事情，把所有可能的情況都看一遍，才能說「找到了目標(biāo)元素」或者「沒找到目標(biāo)元素」。遍歷也稱為窮舉，窮舉的思想在人類看來雖然很不起眼，但借助計(jì)算機(jī)強(qiáng)大的計(jì)算能力，窮舉可以幫助我們解決很多專業(yè)領(lǐng)域知識不能解決的問題。
使用 DFS 來解答剛才題目的代碼如下：
//我們以紅點(diǎn)位置為坐標(biāo){0,0}，綠色位置坐標(biāo)為{2,2}
//目標(biāo)的坐標(biāo)位置
let target = {
x: 0,
y: 0
};
//綠色起點(diǎn)的坐標(biāo)位置
let currentLocation = {
x: 2,
y: 2
};
let used = []; //用來標(biāo)記地圖上哪些點(diǎn)是走過的
let reached = false; //是否能到達(dá)目標(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)相同表示可以抵達(dá)
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 旨在面臨一個路口時，把所有的岔路口都記下來，然后選擇其中一個進(jìn)入，然后將它的分路情況記錄下來，然后再返回來進(jìn)入另外一個岔路，并重復(fù)這樣的操作，用圖形來表示則是這樣的：
從綠色起點(diǎn)出發(fā)，記錄所有的岔路口，并標(biāo)記為走一步可以到達(dá)的。然后選擇其中一個方向走進(jìn)去，我們走綠色左邊（序號為 2）的那個格子，然后將這個路口可走的方向記錄下來并標(biāo)記為 2，意味走兩步可以到達(dá)的地方。
接下來，我們回到起點(diǎn)下面 1 的方塊上（序號為 6），并將它能走的方向也記錄下來，同樣標(biāo)記為 2，因?yàn)橐彩亲邇刹奖憧傻竭_(dá)的地方。這樣走一步以及走兩步可以到達(dá)的地方都搜索完畢了，后續(xù)同理，我們可以把走三步的格子給標(biāo)記出來。
再之后是第四步。我們便成功尋找到了路徑，并且把所有可行的路徑都求出來了。
注意：格子序號分別為 1、4、5 的地方是灰色區(qū)域表示此路不通。
使用 BFS 來解答剛才題目的代碼如下：
//我們以紅點(diǎn)位置為坐標(biāo){0,0}，綠色位置坐標(biāo)為{2,2}
//目標(biāo)的坐標(biāo)位置
let target = {
x: 0,
y: 0
};
//綠色起點(diǎn)的坐標(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; //是否能到達(dá)目標(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)相同表示可以抵達(dá)
reached = true;
console.log('reached: ', reached);
stack = [];
break;
}
}
}
return reached;
}
bfs(target, currentLocation, illegalLocation);「廣度優(yōu)先遍歷」的思想在生活中隨處可見：
- 如果我們要找一個律師，我們會先在朋友中查找，如果沒有找到，繼續(xù)在朋友的朋友中查找，直到找到為止。
- 把一塊石頭投入平靜的水面，激起的一層一層波紋就呈現(xiàn)「廣度優(yōu)先遍歷」的特點(diǎn)。
總結(jié)
- 「一條路走到底，不撞南墻不回頭」是對 DFS 的最直觀描述。因此 DFS 可以借助「遞歸」實(shí)現(xiàn)。
- BFS 呈現(xiàn)出「一層一層向外擴(kuò)張」的特點(diǎn)，先看到的節(jié)點(diǎn)先遍歷，后看到的節(jié)點(diǎn)后遍歷，因此 BFS 可以借助「隊(duì)列」實(shí)現(xiàn)。（遍歷到一個節(jié)點(diǎn)時，如果這個節(jié)點(diǎn)有左（右）孩子節(jié)點(diǎn)，依次將它們加入隊(duì)列。）
- DFS 適合目標(biāo)明確的尋找，而 BFS 適合大范圍的尋找。
到此這篇關(guān)于JavaScript遍歷實(shí)現(xiàn)DFS算法和BFS算法的文章就介紹到這了,更多相關(guān)JavaScript實(shí)現(xiàn)DFS BFS內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在本片文章中，作者將向您講述JavaScript中最鮮為人知的秘密。學(xué)習(xí)js的朋友可以參考下。2011-08-08
JavaScript 實(shí)現(xiàn)鼠標(biāo)拖動元素實(shí)例代碼
這篇文章主要介紹了JavaScript 實(shí)現(xiàn)鼠標(biāo)拖動元素實(shí)例代碼,需要的朋友可以參考下2014-02-02
javascript ASCII和Hex互轉(zhuǎn)的實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猨avascript ASCII和Hex互轉(zhuǎn)的實(shí)現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
原來的腳本當(dāng)只有一張圖片時會彈出JavaScript腳本錯誤，特此將自己修改完的版本貼出。2009-09-09
這篇文章主要為大家詳細(xì)介紹了js實(shí)現(xiàn)自動輪換選項(xiàng)卡，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-01-01
JS面試必備之如何實(shí)現(xiàn)一個精確的倒計(jì)時
又到了金三銀四的季節(jié)了,面試的各位同學(xué)要開始準(zhǔn)備起來了,今天主要分享一個在面試中經(jīng)常被提到的一個面試題：倒計(jì)時,希望對大家有所幫助2024-03-03
在本文中，我將解釋如何使用 setTimeout()，包括如何使用它來制作一個睡眠函數(shù)，使JavaScript暫停執(zhí)行并在連續(xù)的代碼行之間等待。2021-04-04
avalonjs實(shí)現(xiàn)仿微博的圖片拖動特效
JavaScript實(shí)現(xiàn)仿微博的圖片拖動特效，貌似這些天有不少朋友需要這功能，今天發(fā)現(xiàn)這款是js制作的好，不敢獨(dú)享，希望需要的朋友喜歡哦。2015-05-05
TypeScript中declare關(guān)鍵字的具體使用
declare關(guān)鍵字用來告訴編譯器,某個類型是存在的,可以在當(dāng)前文件中使用,本文主要介紹了TypeScript中declare關(guān)鍵字的具體使用,感興趣的可以了解一下2023-10-10
js實(shí)現(xiàn)WebSocket 連接的示例代碼
本文主要介紹了js實(shí)現(xiàn)WebSocket 連接的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-05-05