検索
幅優先検索 (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 までご連絡ください。
カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?カフェインやグアバキャッシュなどのライブラリを使用して、Javaアプリケーションにマルチレベルキャッシュを実装するにはどうすればよいですか?Mar 17, 2025 pm 05:44 PM

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

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

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

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

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

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

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

高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?高度なJavaプロジェクト管理、自動化の構築、依存関係の解像度にMavenまたはGradleを使用するにはどうすればよいですか?Mar 17, 2025 pm 05:46 PM

この記事では、Javaプロジェクト管理、自動化の構築、依存関係の解像度にMavenとGradleを使用して、アプローチと最適化戦略を比較して説明します。

非ブロッキングI/OにJavaのNIO(新しい入出力)APIを使用するにはどうすればよいですか?非ブロッキングI/OにJavaのNIO(新しい入出力)APIを使用するにはどうすればよいですか?Mar 11, 2025 pm 05:51 PM

この記事では、単一のスレッドで複数の接続を効率的に処理するためにセレクターとチャネルを使用して、非ブロッキングI/O用のJavaのNIO APIについて説明します。 プロセス、利点(スケーラビリティ、パフォーマンス)、および潜在的な落とし穴(複雑さ、

適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?適切なバージョン化と依存関係管理を備えたカスタムJavaライブラリ(JARファイル)を作成および使用するにはどうすればよいですか?Mar 17, 2025 pm 05:45 PM

この記事では、MavenやGradleなどのツールを使用して、適切なバージョン化と依存関係管理を使用して、カスタムJavaライブラリ(JARファイル)の作成と使用について説明します。

ネットワーク通信にJavaのソケットAPIを使用するにはどうすればよいですか?ネットワーク通信にJavaのソケットAPIを使用するにはどうすればよいですか?Mar 11, 2025 pm 05:53 PM

この記事では、ネットワーク通信のためのJavaのソケットAPI、クライアントサーバーのセットアップ、データ処理、リソース管理、エラー処理、セキュリティなどの重要な考慮事項をカバーしています。 また、パフォーマンスの最適化手法も調査します

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

ホットツール

mPDF

mPDF

mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

SublimeText3 英語版

SublimeText3 英語版

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

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

このプロジェクトは osdn.net/projects/mingw に移行中です。引き続きそこでフォローしていただけます。 MinGW: GNU Compiler Collection (GCC) のネイティブ Windows ポートであり、ネイティブ Windows アプリケーションを構築するための自由に配布可能なインポート ライブラリとヘッダー ファイルであり、C99 機能をサポートする MSVC ランタイムの拡張機能が含まれています。すべての MinGW ソフトウェアは 64 ビット Windows プラットフォームで実行できます。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強力な PHP 統合開発環境

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境