這篇文章帶給大家的內容是關於JavaScript深度優先遍歷(DFS)和廣度優先遍歷(BFS）演算法的介紹，有一定的參考價值，有需要的朋友可以參考一下，希望對你有所幫助。
背景：在開發頁面的時候，我們有時候會遇到這種需求：在頁面某個dom節點中遍歷，找到目標dom節點，我們正常做法是利用選擇器document.getElementById() ，document.getElementsByName()或document.getElementsByTagName()，但在本文，我們從演算法的角度去尋找dom節點，同時理解深度優先遍歷(DFS)和廣度優先遍歷(BFS)的原理。
準備
假設頁面上的dom結構如下：
<div> <ul> <li> <a> <img alt="JavaScript深度優先遍歷(DFS)和廣度優先遍歷(BFS）演算法的介紹" > </a> </li> <li> <span></span> </li> <li> </li> </ul> <p></p> <button></button> </div>
讓我們來把這個dom結構轉換成樹的樣子
這樣之後，dom結構似乎清楚了不少。
深度優先遍歷（Depth-First Search）
該方法是以縱向的維度對dom樹進行遍歷，從一個dom節點開始，一直遍歷其子節點，直到它的所有子節點都被遍歷完畢之後在遍歷它的兄弟節點。即如圖所示（遍歷順序為紅字鎖標）：
js實作該演算法程式碼(遞歸版本)：
function deepFirstSearch(node,nodeList) {
if (node) {
nodeList.push(node);
var children = node.children;
for (var i = 0; i <p>非遞迴版本： </p><pre class="brush:php;toolbar:false">function deepFirstSearch(node) {
var nodes = [];
if (node != null) {
var stack = [];
stack.push(node);
while (stack.length != 0) {
var item = stack.pop();
nodes.push(item);
var children = item.children;
for (var i = children.length - 1; i >= 0; i--)
stack.push(children[i]);
}
}
return nodes;
}deepFirstSearch接受兩個參數，第一個參數是需要遍歷的節點，第二個是節點所儲存的數組，並且傳回遍歷完之後的數組，該數組的元素順序就是遍歷順序，呼叫方法：
let root = document.getElementById('root')
deepTraversal(root,nodeList=[])控制台輸出結果
廣度優先遍歷（breadth-first traverse）
該方法是以橫向的維度對dom樹進行遍歷，從該節點的第一個子節點開始，遍歷其所有的兄弟節點，再遍歷第一個節點的子節點，完成該遍歷之後，暫時不深入，開始遍歷其兄弟節點的子節點。即如圖所示（遍歷順序為紅字鎖定標）：
js實作演算法程式碼（遞迴版本）：
function breadthFirstSearch(node) {
var nodes = [];
var i = 0;
if (!(node == null)) {
nodes.push(node);
breadthFirstSearch(node.nextElementSibling);
node = nodes[i++];
breadthFirstSearch(node.firstElementChild);
}
return nodes;
}遞迴版本的BFS由於層級太深，會導致堆疊溢出：Maximum call stack size exceeded，但遍歷的順序依舊沒有問題，可以在遍歷過程中進行操作，不返回遍歷數組即可。
非遞迴版本：
function breadthFirstSearch(node) {
var nodes = [];
if (node != null) {
var queue = [];
queue.unshift(node);
while (queue.length != 0) {
var item = queue.shift();
nodes.push(item);
var children = item.children;
for (var i = 0; i <p>控制台輸出結果：</p><p><img src="https://img.php.cn/upload/image/727/585/757/1553909199320348.png" title="1553909199320348.png" alt="JavaScript深度優先遍歷(DFS)和廣度優先遍歷(BFS）演算法的介紹"></p><p style="max-width:90%">#總結：BFS和DFS都是圖的演算法之一，本文所闡述的版本較為簡單，為無向且非連通圖，日後會更新更多基於JavaScript的演算法。 </p><p style="white-space: normal;">這篇文章到這裡就已經全部結束了，更多其他精彩內容可以關注PHP中文網的<a href="http://www.php.cn/course/list/17.html" target="_blank">JavaScript影片教學</a>專欄！ </p><p></p>#以上是JavaScript深度優先遍歷(DFS)和廣度優先遍歷(BFS）演算法的介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！
