JavaScript深度優(yōu)先遍歷DFS和廣度優(yōu)先遍歷BFS算法的示例-創(chuàng)新互聯(lián)

小編給大家分享一下JavaScript深度優(yōu)先遍歷DFS和廣度優(yōu)先遍歷BFS算法的示例，希望大家閱讀完這篇文章后大所收獲，下面讓我們一起去探討吧！

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供富裕網(wǎng)站建設(shè)、富裕做網(wǎng)站、富裕網(wǎng)站設(shè)計(jì)、富裕網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、富裕企業(yè)網(wǎng)站模板建站服務(wù)，十余年富裕做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

背景：在開(kāi)發(fā)頁(yè)面的時(shí)候，我們有時(shí)候會(huì)遇到這種需求：在頁(yè)面某個(gè)dom節(jié)點(diǎn)中遍歷，找到目標(biāo)dom節(jié)點(diǎn)，我們正常做法是利用選擇器document.getElementById()，document.getElementsByName()或者document.getElementsByTagName()，但在本文，我們從算法的角度去查找dom節(jié)點(diǎn)，同時(shí)理解一下深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)的原理。

準(zhǔn)備

假設(shè)頁(yè)面上的dom結(jié)構(gòu)如下：

<div id="root">
    <ul>
        <li>
            <a href="">
                <img src="" alt="">
            </a>
        </li>
        <li>
            <span></span>
        </li>
        <li>
        </li>
    </ul>
    <p></p>
    <button></button>
</div>

讓我們來(lái)把這個(gè)dom結(jié)構(gòu)轉(zhuǎn)化成樹(shù)的樣子

這樣之后，dom結(jié)構(gòu)似乎清楚了不少。

深度優(yōu)先遍歷（Depth-First Search）

該方法是以縱向的維度對(duì)dom樹(shù)進(jìn)行遍歷，從一個(gè)dom節(jié)點(diǎn)開(kāi)始，一直遍歷其子節(jié)點(diǎn)，直到它的所有子節(jié)點(diǎn)都被遍歷完畢之后在遍歷它的兄弟節(jié)點(diǎn)。即如圖所示（遍歷順序?yàn)榧t字鎖標(biāo)）：

js實(shí)現(xiàn)該算法代碼(遞歸版本)：

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i < children.length; i++) 
        //每次遞歸的時(shí)候?qū)?需要遍歷的節(jié)點(diǎn) 和 節(jié)點(diǎn)所存儲(chǔ)的數(shù)組傳下去
        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接受兩個(gè)參數(shù)，第一個(gè)參數(shù)是需要遍歷的節(jié)點(diǎn)，第二個(gè)是節(jié)點(diǎn)所存儲(chǔ)的數(shù)組，并且返回遍歷完之后的數(shù)組，該數(shù)組的元素順序就是遍歷順序，調(diào)用方法：

let root = document.getElementById('root')
deepTraversal(root,nodeList=[])

控制臺(tái)輸出結(jié)果

廣度優(yōu)先遍歷（breadth-first traverse）

該方法是以橫向的維度對(duì)dom樹(shù)進(jìn)行遍歷，從該節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)開(kāi)始，遍歷其所有的兄弟節(jié)點(diǎn)，再遍歷第一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)，完成該遍歷之后，暫時(shí)不深入，開(kāi)始遍歷其兄弟節(jié)點(diǎn)的子節(jié)點(diǎn)。即如圖所示（遍歷順序?yàn)榧t字鎖標(biāo)）：

js實(shí)現(xiàn)算法代碼（遞歸版本）：

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由于層級(jí)太深，會(huì)導(dǎo)致堆棧溢出：Maximum call stack size exceeded，但遍歷的順序依舊沒(méi)有問(wèn)題，可以在遍歷過(guò)程中進(jìn)行操作，不返回遍歷數(shù)組即可。

非遞歸版本：

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;  
}

控制臺(tái)輸出結(jié)果：

總結(jié)：BFS和DFS都是圖的算法之一，本文所闡述的版本較為簡(jiǎn)單，為無(wú)向且非連通圖，在日后會(huì)更新更多基于JavaScript的算法。

看完了這篇文章，相信你對(duì)JavaScript深度優(yōu)先遍歷DFS和廣度優(yōu)先遍歷BFS算法的示例有了一定的了解，想了解更多相關(guān)知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)網(wǎng)站制作公司行業(yè)資訊頻道，感謝各位的閱讀！

文章題目：JavaScript深度優(yōu)先遍歷DFS和廣度優(yōu)先遍歷BFS算法的示例-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://www.muchs.cn/article48/deojhp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供自適應(yīng)網(wǎng)站、云服務(wù)器、做網(wǎng)站、網(wǎng)站建設(shè)、建站公司、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)