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

roadtogeek 發(fā)布于2019-08-23 16:33 / 1391人閱讀

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

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

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

準備

假設頁面上的dom結構如下：

讓我們來把這個dom結構轉化成樹的樣子

這樣之后，dom結構似乎清楚了不少。

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

該方法是以縱向的維度對dom樹進行遍歷，從一個dom節(jié)點開始，一直遍歷其子節(jié)點，直到它的所有子節(jié)點都被遍歷完畢之后在遍歷它的兄弟節(jié)點。即如圖所示（遍歷順序為紅字鎖標）：

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

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

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

控制臺輸出結果

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

該方法是以橫向的維度對dom樹進行遍歷，從該節(jié)點的第一個子節(jié)點開始，遍歷其所有的兄弟節(jié)點，再遍歷第一個節(jié)點的子節(jié)點，完成該遍歷之后，暫時不深入，開始遍歷其兄弟節(jié)點的子節(jié)點。即如圖所示（遍歷順序為紅字鎖標）：

js實現(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由于層級太深，會導致堆棧溢出：Maximum call stack size exceeded，但遍歷的順序依舊沒有問題，可以在遍歷過程中進行操作，不返回遍歷數(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;  
}

控制臺輸出結果：

總結

BFS和DFS都是圖的算法之一，本文所闡述的版本較為簡單，為無向且非連通圖，在日后會更新更多基于JavaScript的算法。

云服務器 GPU云服務器廣度優(yōu)先遍歷廣度優(yōu)先搜索算法代碼廣度優(yōu)先搜索 python廣度優(yōu)先

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/103144.html

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

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

Yuanf 2019-08-23 11:38 評論0 收藏0
js版本的BFS&DFS

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

劉福 2019-08-22 16:49 評論0 收藏0
Javascript的數(shù)據(jù)結構與算法(三)

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

MasonEast 2019-08-21 11:24 評論0 收藏0
DOM樹遍歷之JS實現(xiàn)DFS&BFS

摘要：對于上面例子遍歷結果應為則總是先遍歷當前層級的所有節(jié)點，只有當當前層級所有節(jié)點都遍歷結束后才會進入下一層級。我們一般可以采用DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）來遍歷DOM樹介紹 DFS & BFS 我們來結合具體例子進行分析，給出HTML代碼片段如下： DFS總是先進入下一...

imccl 2019-08-20 15:52 評論0 收藏0
DOM樹遍歷之JS實現(xiàn)DFS&BFS

摘要：對于上面例子遍歷結果應為則總是先遍歷當前層級的所有節(jié)點，只有當當前層級所有節(jié)點都遍歷結束后才會進入下一層級。我們一般可以采用DFS（深度優(yōu)先遍歷）和BFS（廣度優(yōu)先遍歷）來遍歷DOM樹介紹 DFS & BFS 我們來結合具體例子進行分析，給出HTML代碼片段如下： DFS總是先進入下一...

fengxiuping 2019-08-01 16:40 評論0 收藏0