検索
ホームページウェブフロントエンドjsチュートリアル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 構造をツリーに変換しましょう

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

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

深さ優先検索

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

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

アルゴリズムを実装するための 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=[])

コンソール出力結果

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

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

このメソッドは水平方向です。ノードの最初の子ノードから開始して、そのすべての兄弟ノードを走査し、次に最初のノードの子ノードを走査して、DOM ツリーを次元的に走査します。走査が完了した後は、次のステップには進みません。当面は深さを設定し、その兄弟ノードのトラバースを開始します。つまり、図に示すように (走査順序は赤い鍵マークです):

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

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 サイトの他の関連記事を参照してください。

声明
この記事はsegmentfaultで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。
Python vs. JavaScript:学習曲線と使いやすさPython vs. JavaScript:学習曲線と使いやすさApr 16, 2025 am 12:12 AM

Pythonは、スムーズな学習曲線と簡潔な構文を備えた初心者により適しています。 JavaScriptは、急な学習曲線と柔軟な構文を備えたフロントエンド開発に適しています。 1。Python構文は直感的で、データサイエンスやバックエンド開発に適しています。 2。JavaScriptは柔軟で、フロントエンドおよびサーバー側のプログラミングで広く使用されています。

Python vs. JavaScript:コミュニティ、ライブラリ、リソースPython vs. JavaScript:コミュニティ、ライブラリ、リソースApr 15, 2025 am 12:16 AM

PythonとJavaScriptには、コミュニティ、ライブラリ、リソースの観点から、独自の利点と短所があります。 1)Pythonコミュニティはフレンドリーで初心者に適していますが、フロントエンドの開発リソースはJavaScriptほど豊富ではありません。 2)Pythonはデータサイエンスおよび機械学習ライブラリで強力ですが、JavaScriptはフロントエンド開発ライブラリとフレームワークで優れています。 3)どちらも豊富な学習リソースを持っていますが、Pythonは公式文書から始めるのに適していますが、JavaScriptはMDNWebDocsにより優れています。選択は、プロジェクトのニーズと個人的な関心に基づいている必要があります。

C/CからJavaScriptへ:すべてがどのように機能するかC/CからJavaScriptへ:すべてがどのように機能するかApr 14, 2025 am 12:05 AM

C/CからJavaScriptへのシフトには、動的なタイピング、ゴミ収集、非同期プログラミングへの適応が必要です。 1)C/Cは、手動メモリ管理を必要とする静的に型付けられた言語であり、JavaScriptは動的に型付けされ、ごみ収集が自動的に処理されます。 2)C/Cはマシンコードにコンパイルする必要がありますが、JavaScriptは解釈言語です。 3)JavaScriptは、閉鎖、プロトタイプチェーン、約束などの概念を導入します。これにより、柔軟性と非同期プログラミング機能が向上します。

JavaScriptエンジン:実装の比較JavaScriptエンジン:実装の比較Apr 13, 2025 am 12:05 AM

さまざまなJavaScriptエンジンは、各エンジンの実装原則と最適化戦略が異なるため、JavaScriptコードを解析および実行するときに異なる効果をもたらします。 1。語彙分析:ソースコードを語彙ユニットに変換します。 2。文法分析:抽象的な構文ツリーを生成します。 3。最適化とコンパイル:JITコンパイラを介してマシンコードを生成します。 4。実行:マシンコードを実行します。 V8エンジンはインスタントコンピレーションと非表示クラスを通じて最適化され、Spidermonkeyはタイプ推論システムを使用して、同じコードで異なるパフォーマンスパフォーマンスをもたらします。

ブラウザを超えて:現実世界のJavaScriptブラウザを超えて:現実世界のJavaScriptApr 12, 2025 am 12:06 AM

現実世界におけるJavaScriptのアプリケーションには、サーバー側のプログラミング、モバイルアプリケーション開発、モノのインターネット制御が含まれます。 2。モバイルアプリケーションの開発は、ReactNativeを通じて実行され、クロスプラットフォームの展開をサポートします。 3.ハードウェアの相互作用に適したJohnny-Fiveライブラリを介したIoTデバイス制御に使用されます。

next.jsを使用してマルチテナントSaaSアプリケーションを構築する(バックエンド統合)next.jsを使用してマルチテナントSaaSアプリケーションを構築する(バックエンド統合)Apr 11, 2025 am 08:23 AM

私はあなたの日常的な技術ツールを使用して機能的なマルチテナントSaaSアプリケーション(EDTECHアプリ)を作成しましたが、あなたは同じことをすることができます。 まず、マルチテナントSaaSアプリケーションとは何ですか? マルチテナントSaaSアプリケーションを使用すると、Singの複数の顧客にサービスを提供できます

next.jsを使用してマルチテナントSaaSアプリケーションを構築する方法(フロントエンド統合)next.jsを使用してマルチテナントSaaSアプリケーションを構築する方法(フロントエンド統合)Apr 11, 2025 am 08:22 AM

この記事では、許可によって保護されたバックエンドとのフロントエンド統合を示し、next.jsを使用して機能的なedtech SaaSアプリケーションを構築します。 FrontEndはユーザーのアクセス許可を取得してUIの可視性を制御し、APIリクエストがロールベースに付着することを保証します

JavaScript:Web言語の汎用性の調査JavaScript:Web言語の汎用性の調査Apr 11, 2025 am 12:01 AM

JavaScriptは、現代のWeb開発のコア言語であり、その多様性と柔軟性に広く使用されています。 1)フロントエンド開発:DOM操作と最新のフレームワーク(React、Vue.JS、Angularなど)を通じて、動的なWebページとシングルページアプリケーションを構築します。 2)サーバー側の開発:node.jsは、非ブロッキングI/Oモデルを使用して、高い並行性とリアルタイムアプリケーションを処理します。 3)モバイルおよびデスクトップアプリケーション開発:クロスプラットフォーム開発は、反応および電子を通じて実現され、開発効率を向上させます。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

VSCode Windows 64 ビットのダウンロード

VSCode Windows 64 ビットのダウンロード

Microsoft によって発売された無料で強力な IDE エディター

SublimeText3 英語版

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境