JavaScript 深さ優先トラバーサル (DFS) および幅優先トラバーサル (BFS) アルゴリズムの概要

この記事では、JavaScript の深さ優先トラバーサル (DFS) および幅優先トラバーサル (BFS) アルゴリズムについて説明します。これには一定の参考価値があります。必要な友人は参照できます。お役に立てば幸いです。 . 助かりました。

背景: ページを開発するとき、ターゲットの dom ノードを見つけるためにページ上の特定の dom ノードをトラバースする必要があることがあります。通常のアプローチは、セレクター document.getElementById() 、 document.getElementsByName を使用することです。 () または document.getElementsByTagName() を使用しますが、この記事ではアルゴリズムの観点から dom ノードを探し、同時に深さ優先トラバーサル (DFS) と幅優先トラバーサル (BFS) の原理を理解します。

準備

ページ上の dom 構造が次のとおりであると仮定します。

<div>
    <ul>
        <li>
            <a>
                <img  src="/static/imghwm/default1.png" data-src="" class="lazy" alt="JavaScript 深さ優先トラバーサル (DFS) および幅優先トラバーサル (BFS) アルゴリズムの概要" >
            </a>
        </li>
        <li>
            <span></span>
        </li>
        <li>
        </li>
    </ul>
    <p></p>
    <button></button>
</div>

この dom 構造をツリーに変換しましょう

これ以降、dom の構造がより明確になったように見えます。

深さ優先検索

このメソッドは、dom ノードから開始してその子ノードをすべて横断するまで、dom ツリーを垂直方向に横断します。すべての子ノードが横断された後、その兄弟ノードが横断されます。図に示すように (走査順序は赤い鍵マークです):

アルゴリズムを実装するための js コード (再帰バージョン):

function deepFirstSearch(node,nodeList) {  
    if (node) {    
        nodeList.push(node);    
        var children = node.children;    
        for (var i = 0; i <p>Non -再帰バージョン: </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 は 2 つのパラメータを受け入れます。最初のパラメータは、走査する必要があるノードです。2 番目のパラメータは、ノードに格納されている配列であり、走査後に配列を返します。配列の要素は走査順序です。呼び出しメソッド:

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

コンソール出力結果

幅優先走査 (幅優先走査)

このメソッドは水平方向です。ノードの最初の子ノードから開始して、そのすべての兄弟ノードを走査し、次に最初のノードの子ノードを走査して、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 の再帰バージョンは、レベルが深すぎるとスタック オーバーフローが発生するためです: 最大呼び出しスタック サイズを超えましたが、トラバーサルの順序にはまだ問題はありません。トラバーサル プロセス中に、クエリを返さずに操作を実行できます。走査された配列。

非再帰バージョン:

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="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/image/727/585/757/1553909199320348.png?x-oss-process=image/resize,p_40" class="lazy" title="1553909199320348.png" alt="JavaScript 深さ優先トラバーサル (DFS) および幅優先トラバーサル (BFS) アルゴリズムの概要"></p><p   style="max-width:90%">概要: BFS と DFS はどちらもグラフ アルゴリズムです。この記事は比較的単純で、無向で接続されていないグラフです。今後、さらに多くの JavaScript ベースのアルゴリズムが更新される予定です。 </p><p style="white-space: normal;">この記事はここで終了しました。その他のエキサイティングなコンテンツについては、PHP 中国語 Web サイトの <a href="http://www.php.cn/course/list/17.html" target="_blank">JavaScript ビデオ チュートリアル</a> 列に注目してください。 </p><p></p>

以上がJavaScript 深さ優先トラバーサル (DFS) および幅優先トラバーサル (BFS) アルゴリズムの概要の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。