小編給大家分享一下JavaScript深度優先遍歷DFS和廣度優先遍歷BFS算法的示例,希望大家閱讀完這篇文章后大所收獲,下面讓我們一起去探討吧!
創新互聯公司專業為企業提供富裕網站建設、富裕做網站、富裕網站設計、富裕網站制作等企業網站建設、網頁設計與制作、富裕企業網站模板建站服務,十余年富裕做網站經驗,不只是建網站,更提供有價值的思路和整體網絡服務。背景:在開發頁面的時候,我們有時候會遇到這種需求:在頁面某個dom節點中遍歷,找到目標dom節點,我們正常做法是利用選擇器document.getElementById(),document.getElementsByName()或者document.getElementsByTagName(),但在本文,我們從算法的角度去查找dom節點,同時理解一下深度優先遍歷(DFS)和廣度優先遍歷(BFS)的原理。
準備
假設頁面上的dom結構如下:
<div id="root"> <ul> <li> <a href=""> <img src="" alt=""> </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 < children.length; i++) //每次遞歸的時候將 需要遍歷的節點 和 節點所存儲的數組傳下去 deepFirstSearch(children[i],nodeList); } return nodeList; }
非遞歸版本:
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 < children.length; i++) queue.push(children[i]); } } return nodes; }
控制臺輸出結果:
總結:BFS和DFS都是圖的算法之一,本文所闡述的版本較為簡單,為無向且非連通圖,在日后會更新更多基于JavaScript的算法。
看完了這篇文章,相信你對JavaScript深度優先遍歷DFS和廣度優先遍歷BFS算法的示例有了一定的了解,想了解更多相關知識,歡迎關注創新互聯網站制作公司行業資訊頻道,感謝各位的閱讀!
文章題目:JavaScript深度優先遍歷DFS和廣度優先遍歷BFS算法的示例-創新互聯
本文網址:http://m.newbst.com/article48/deojhp.html
成都網站建設公司_創新互聯,為您提供自適應網站、云服務器、做網站、網站建設、建站公司、定制網站
聲明:本網站發布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創新互聯