国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS)

roadtogeek / 1382人閱讀

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

JS算法之深度優(yōu)先遍歷(DFS)和廣度優(yōu)先遍歷(BFS) 背景

在開(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)如下:

讓我們來(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的算法。

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/103144.html

相關(guān)文章

  • js 中二叉樹(shù)的深度遍歷廣度遍歷(遞歸實(shí)現(xiàn)與非遞歸實(shí)現(xiàn))

    摘要:樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度或高度。二叉樹(shù)有深度遍歷和廣度遍歷,深度遍歷有前序中序和后序三種遍歷方法。二叉樹(shù)的前序遍歷可以用來(lái)顯示目錄結(jié)構(gòu)等中序遍歷可以實(shí)現(xiàn)表達(dá)式樹(shù),在編譯器底層很有用后序遍歷可以用來(lái)實(shí)現(xiàn)計(jì)算目錄內(nèi)的文件及其信息等。 樹(shù)的簡(jiǎn)介 棧、隊(duì)列、鏈表等數(shù)據(jù)結(jié)構(gòu),都是順序數(shù)據(jù)結(jié)構(gòu)。而樹(shù)是非順序數(shù)據(jù)結(jié)構(gòu)。樹(shù)型結(jié)構(gòu)是一類非常重要的非線性結(jié)構(gòu)。直觀地,樹(shù)型結(jié)構(gòu)是以分支關(guān)系定義的層次結(jié)...

    Yuanf 評(píng)論0 收藏0
  • js版本的BFS&DFS

    摘要:隊(duì)列棧隊(duì)列是先進(jìn)先出,后進(jìn)后出,常用的操作是取第一個(gè)元素尾部加入一個(gè)元素。棧是后進(jìn)先出,就像一個(gè)垃圾桶,后入的垃圾先被倒出來(lái)。遍歷中間過(guò)程,每一個(gè)節(jié)點(diǎn)入棧的時(shí)候是灰色的,出棧的時(shí)候是黑色的。 0. 前言 廣度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS),大家可能在oj上見(jiàn)過(guò),各種求路徑、最短路徑、最優(yōu)方法、組合等等。于是,我們不妨動(dòng)手試一下js版本怎么玩。 1.隊(duì)列、棧 隊(duì)列是先進(jìn)先出,...

    劉福 評(píng)論0 收藏0
  • Javascript的數(shù)據(jù)結(jié)構(gòu)與算法(三)

    摘要:存在好幾種方式來(lái)表示這種數(shù)據(jù)結(jié)構(gòu)。下面的示意圖展示了鄰接表數(shù)據(jù)結(jié)構(gòu)。在關(guān)聯(lián)矩陣中矩陣的行表示頂點(diǎn)列表示邊。廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法基本上是相同的只有一點(diǎn)不同那就是待訪問(wèn)頂點(diǎn)列表的數(shù)據(jù)結(jié)構(gòu)。 1 樹(shù) 一個(gè)樹(shù)結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)(除了頂部的第一個(gè)節(jié)點(diǎn))以及零個(gè)或多個(gè)子節(jié)點(diǎn)。位于樹(shù)頂部的節(jié)點(diǎn)叫作根節(jié)點(diǎn)(11)。它沒(méi)有父節(jié)點(diǎn)。樹(shù)中的每個(gè)元素都叫作...

    MasonEast 評(píng)論0 收藏0
  • DOM樹(shù)遍歷JS實(shí)現(xiàn)DFS&BFS

    摘要:對(duì)于上面例子遍歷結(jié)果應(yīng)為則總是先遍歷當(dāng)前層級(jí)的所有節(jié)點(diǎn),只有當(dāng)當(dāng)前層級(jí)所有節(jié)點(diǎn)都遍歷結(jié)束后才會(huì)進(jìn)入下一層級(jí)。 我們一般可以采用DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)來(lái)遍歷DOM樹(shù) 介紹 DFS & BFS 我們來(lái)結(jié)合具體例子進(jìn)行分析,給出HTML代碼片段如下: DFS總是先進(jìn)入下一...

    imccl 評(píng)論0 收藏0
  • DOM樹(shù)遍歷JS實(shí)現(xiàn)DFS&BFS

    摘要:對(duì)于上面例子遍歷結(jié)果應(yīng)為則總是先遍歷當(dāng)前層級(jí)的所有節(jié)點(diǎn),只有當(dāng)當(dāng)前層級(jí)所有節(jié)點(diǎn)都遍歷結(jié)束后才會(huì)進(jìn)入下一層級(jí)。 我們一般可以采用DFS(深度優(yōu)先遍歷)和BFS(廣度優(yōu)先遍歷)來(lái)遍歷DOM樹(shù) 介紹 DFS & BFS 我們來(lái)結(jié)合具體例子進(jìn)行分析,給出HTML代碼片段如下: DFS總是先進(jìn)入下一...

    fengxiuping 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<