検索
幅優先検索 (BFS)Aug 10, 2024 am 06:43 AM

グラフの幅優先検索では、レベルごとに頂点を訪問します。最初のレベルは開始頂点で構成されます。次の各レベルは、前のレベルの頂点に隣接する頂点で構成されます。グラフの幅優先走査は、ツリー走査で説明したツリーの幅優先走査に似ています。ツリーの幅優先走査では、ノードはレベルごとにアクセスされます。最初にルートがアクセスされ、次にルートのすべての子がアクセスされ、次にルートの孫がアクセスされます。同様に、グラフの幅優先検索では、最初に頂点を訪問し、次にその頂点に隣接するすべての頂点を訪問し、次にそれらの頂点に隣接するすべての頂点を訪問する、というように続きます。各頂点が 1 回だけ訪問されるようにするため、すでに訪問されている頂点はスキップされます。

幅優先検索アルゴリズム

グラフの頂点 v から開始する幅優先検索のアルゴリズムは、以下のコードで説明されています。

入力: G = (V, E) および開始頂点 v
出力: v
をルートとする BFS ツリー 1 ツリー bfs(頂点 v) {
2 訪問する頂点を格納するための空のキューを作成します。
3 v をキューに追加します;
4 マーク v が訪問しました;
5
6 while (キューは空ではありません) {
7 頂点、たとえば u をキューからデキューします。
8 通過した頂点のリストに u を追加します。
あなたたちの隣人ごとに 9
w がまだ訪問されていない場合は 10 {
11 w をキューに追加します;
12 u をツリー内の w の親として設定します;
13 マークを訪問しました;
14 }
15 }
16 }

下図 (a) のグラフを考えてみましょう。頂点 0 から幅優先検索を開始するとします。下の図 (b) に示すように、最初に 0 を訪問し、次にその隣接する頂点 1、2、および 3 をすべて訪問します。頂点 1 には、0、2、および 4 という 3 つの近傍があります。0 と 2 はすでに訪問されているため、次の図 (c) に示すように、ここでは 4 だけを訪問します。頂点 2 には 3 つの近傍、0、1、および 3 があり、これらはすべて訪問済みです。頂点 3 には 3 つの近傍、0、2、および 4 があり、これらはすべて訪問されています。頂点 4 には 2 つの隣接ノード 1 と 3 があり、これらはすべて訪問済みです。したがって、検索は終了します。

Breadth-First Search (BFS)

各エッジと各頂点は 1 回だけ訪問されるため、bfs メソッドの時間計算量は O(|E| + |V|) です。ここで、| E| はエッジの数を示し、|V| は頂点の数を示します。

幅優先検索の実装

bfs(int v) メソッドは、Graph インターフェースで定義され、AbstractGraph.java クラスに実装されます (197 ~ 222 行目)。これは、頂点 v をルートとする Tree クラスのインスタンスを返します。このメソッドは、検索された頂点をリスト searchOrder (198 行目) に保存し、各頂点の親を配列 parent (199 行目) に保存し、キューのリンク リストを使用します (行 199)。 203–204)、isVisited 配列を使用して頂点が訪問されたかどうかを示します (207 行目)。検索は頂点 v から開始されます。 v は 206 行目でキューに追加され、訪問済みとしてマークされます (207 行目)。このメソッドはキュー内の各頂点 u を検査し (210 行目)、それを searchOrder に追加します (211 行目)。このメソッドは、u の未訪問の各ネイバー e.v をキューに追加し (214 行目)、その親を u に設定し (215 行目)、訪問済みとしてマークします。 (行 216).

Breadth-First Search (BFS)

以下のコードは、シカゴから始まる上図のグラフの BFS を表示するテスト プログラムを提供します。

public class TestBFS {

    public static void main(String[] args) {
        String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};

        int[][] edges = {
                {0, 1}, {0, 3}, {0, 5},
                {1, 0}, {1, 2}, {1, 3},
                {2, 1}, {2, 3}, {2, 4}, {2, 10},
                {3, 0}, {3, 1}, {3, 2}, {3, 4}, {3, 5},
                {4, 2}, {4, 3}, {4, 5}, {4, 7}, {4, 8}, {4, 10},
                {5, 0}, {5, 3}, {5, 4}, {5, 6}, {5, 7},
                {6, 5}, {6, 7},
                {7, 4}, {7, 5}, {7, 6}, {7, 8},
                {8, 4}, {8, 7}, {8, 9}, {8, 10}, {8, 11},
                {9, 8}, {9, 11},
                {10, 2}, {10, 4}, {10, 8}, {10, 11},
                {11, 8}, {11, 9}, {11, 10}
        };

        Graph<string> graph = new UnweightedGraph(vertices, edges);
        AbstractGraph<string>.Tree bfs = graph.bfs(graph.getIndex("Chicago"));

        java.util.List<integer> searchOrders = bfs.getSearchOrder();
        System.out.println(bfs.getNumberOfVerticesFound() + " vertices are searched in this BFS order:");
        for(int i = 0; i 



<p>12 個の頂点が次の順序で検索されます:<br>
 シカゴ シアトル デンバー カンザスシティ ボストン ニューヨーク<br>
 サンフランシスコ ロサンゼルス アトランタ ダラス マイアミ ヒューストン<br>
シアトルの親はシカゴです<br>
サンフランシスコの親はシアトルです<br>
ロサンゼルスの親はデンバーです<br>
デンバーの親はシカゴです<br>
カンザスシティの親はシカゴです<br>
ボストンの親はシカゴです<br>
ニューヨークの親はシカゴです<br>
アトランタの親はカンザスシティです<br>
マイアミの親はアトランタです<br>
ダラスの親はカンザスシティです<br>
ヒューストンの親はアトランタです</p>

<h2>
  
  
  BFS のアプリケーション
</h2>

<p>DFS によって解決される問題の多くは、BFS を使用しても解決できます。具体的には、BFS を使用して次の問題を解決できます。</p>
<ul>
<li>グラフが接続されているかどうかを検出します。グラフ内の任意の 2 つの頂点間にパスがある場合、グラフは接続されています。</li>
<li>2 つの頂点間にパスがあるかどうかを検出します。</li>
<li>2 つの頂点間の最短経路を見つけます。ルートと BFS ツリー内の任意のノード間のパスが、ルートとノード間の最短パスであることを証明できます。</li>
<li>接続されているすべてのコンポーネントを検索します。連結コンポーネントは、頂点のすべてのペアがパスによって接続されている最大連結部分グラフです。</li>
<li>グラフに周期があるかどうかを検出します。</li>
<li>グラフ内のサイクルを見つけます。</li>
<li>グラフが 2 部であるかどうかをテストします。 (同じセット内の頂点間にエッジが存在しないように、グラフの頂点を 2 つの互いに素なセットに分割できる場合、グラフは 2 部構成です。)</li>
</ul>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/172324339470608.png?x-oss-process=image/resize,p_40" class="lazy" alt="Breadth-First Search (BFS)"></p>


          

            
        </integer></string></string>

以上が幅優先検索 (BFS)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、Svelte2025年のトップ4 JavaScriptフレームワーク:React、Angular、Vue、SvelteMar 07, 2025 pm 06:09 PM

この記事では、2025年の上位4つのJavaScriptフレームワーク(React、Angular、Vue、Svelte)を分析し、パフォーマンス、スケーラビリティ、将来の見通しを比較します。 強力なコミュニティと生態系のためにすべてが支配的なままですが、彼らの相対的なポップ

Spring Boot Snakeyaml 2.0 CVE-2022-1471問題修正Spring Boot Snakeyaml 2.0 CVE-2022-1471問題修正Mar 07, 2025 pm 05:52 PM

この記事では、リモートコードの実行を可能にする重大な欠陥であるSnakeyamlのCVE-2022-1471の脆弱性について説明します。 Snakeyaml 1.33以降のSpring Bootアプリケーションをアップグレードする方法は、このリスクを軽減する方法を詳述し、その依存関係のアップデートを強調しています

カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?Mar 17, 2025 pm 05:44 PM

この記事では、カフェインとグアバキャッシュを使用してJavaでマルチレベルキャッシュを実装してアプリケーションのパフォーマンスを向上させています。セットアップ、統合、パフォーマンスの利点をカバーし、構成と立ち退きポリシー管理Best Pra

Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Javaのクラスロードメカニズムは、さまざまなクラスローダーやその委任モデルを含むどのように機能しますか?Mar 17, 2025 pm 05:35 PM

Javaのクラスロードには、ブートストラップ、拡張機能、およびアプリケーションクラスローダーを備えた階層システムを使用して、クラスの読み込み、リンク、および初期化が含まれます。親の委任モデルは、コアクラスが最初にロードされ、カスタムクラスのLOAに影響を与えることを保証します

node.js 20:キーパフォーマンスが向上し、新機能node.js 20:キーパフォーマンスが向上し、新機能Mar 07, 2025 pm 06:12 PM

node.js 20は、V8エンジンの改善、特により速いガベージコレクションとI/Oを介してパフォーマンスを大幅に向上させます。 新機能には、より良いWebセンブリのサポートと洗練されたデバッグツール、開発者の生産性とアプリケーション速度の向上が含まれます。

Iceberg:データレイクテーブルの未来Iceberg:データレイクテーブルの未来Mar 07, 2025 pm 06:31 PM

大規模な分析データセットのオープンテーブル形式であるIcebergは、データの湖のパフォーマンスとスケーラビリティを向上させます。 内部メタデータ管理を通じて、寄木細工/ORCの制限に対処し、効率的なスキーマの進化、タイムトラベル、同時wを可能にします

Javaで機能的なプログラミング技術を実装するにはどうすればよいですか?Javaで機能的なプログラミング技術を実装するにはどうすればよいですか?Mar 11, 2025 pm 05:51 PM

この記事では、Lambda式、Streams API、メソッド参照、およびオプションを使用して、機能プログラミングをJavaに統合することを調べます。 それは、簡潔さと不変性を通じてコードの読みやすさと保守性の改善などの利点を強調しています

キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPA(Java Persistence API)を使用するにはどうすればよいですか?Mar 17, 2025 pm 05:43 PM

この記事では、キャッシュや怠zyなロードなどの高度な機能を備えたオブジェクトリレーショナルマッピングにJPAを使用することについて説明します。潜在的な落とし穴を強調しながら、パフォーマンスを最適化するためのセットアップ、エンティティマッピング、およびベストプラクティスをカバーしています。[159文字]

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ヘンタイを無料で生成します。

ホットツール

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

SublimeText3 英語版

SublimeText3 英語版

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

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境