java graph tutorial how implement graph data structure
この包括的なJavaグラフチュートリアルでは、グラフのデータ構造について詳しく説明します。 Javaでグラフを作成、実装、表現、トラバースする方法が含まれています。
グラフのデータ構造は、主にさまざまなポイントを接続するネットワークを表します。これらのポイントは頂点と呼ばれ、これらの頂点を接続するリンクは「エッジ」と呼ばれます。したがって、グラフgは、これらの頂点を接続する頂点VとエッジEのセットとして定義されます。
グラフは主に、コンピュータネットワーク、ソーシャルネットワークなどのさまざまなネットワークを表すために使用されます。また、ソフトウェアやアーキテクチャのさまざまな依存関係を表すためにも使用できます。これらの依存関係グラフは、ソフトウェアの分析やデバッグに非常に役立ちます。
=> ここですべてのJavaチュートリアルを確認してください。
学習内容:
Javaグラフのデータ構造
以下に示すのは、5つの頂点{A、B、C、D、E}と、{{AB}、{AC}、{AD}、{BD}、{CE}、{ED}}で与えられるエッジを持つグラフです。エッジに方向が表示されないため、このグラフは「無向グラフ」と呼ばれます。
上に示した無向グラフとは別に、Javaにはグラフのいくつかのバリエーションがあります。
これらのバリアントについて詳しく説明しましょう。
循環二重リンクリストc ++
グラフのさまざまなバリエーション
以下は、グラフのバリエーションの一部です。
#1)有向グラフ
有向グラフまたは有向グラフは、エッジが特定の方向を持っているグラフデータ構造です。それらは1つの頂点から始まり、別の頂点に到達します。
次の図は、有向グラフの例を示しています。
上の図では、頂点Aから頂点Bにエッジがあります。ただし、BからAにエッジが指定されていない限り、AからBは無向グラフのようにBからAと同じではないことに注意してください。
最初と最後の頂点が同じであるパスが少なくとも1つある場合、有向グラフは循環的です。上の図では、パスA-> B-> C-> D-> E-> Aが有向閉路グラフまたは閉路グラフを形成しています。
逆に、有向非巡回グラフは、有向サイクルがない、つまりサイクルを形成するパスがないグラフです。
#2)加重グラフ
重み付きグラフでは、重みグラフの各エッジに関連付けられています。重みは通常、2つの頂点間の距離を示します。次の図は、加重グラフを示しています。方向が示されていないため、これは無向グラフです。
加重グラフは有向または無向にできることに注意してください。
グラフを作成する方法は?
Javaは、グラフデータ構造の本格的な実装を提供していません。ただし、Javaのコレクションを使用してプログラムでグラフを表すことはできます。ベクトルのような動的配列を使用してグラフを実装することもできます。
通常、HashMapコレクションを使用してJavaでグラフを実装します。 HashMap要素は、キーと値のペアの形式です。グラフの隣接リストをHashMapで表すことができます。
グラフを作成する最も一般的な方法は、隣接行列や隣接リストなどのグラフの表現の1つを使用することです。次に、これらの表現について説明し、次にArrayListを使用する隣接リストを使用してJavaでグラフを実装します。
Javaでのグラフ表現
グラフ表現とは、グラフデータをコンピュータのメモリに保存するためのアプローチまたは手法を意味します。
以下に示すように、グラフには2つの主要な表現があります。
隣接行列
隣接行列は、グラフの線形表現です。このマトリックスは、グラフの頂点とエッジのマッピングを格納します。隣接行列では、グラフの頂点は行と列を表します。これは、グラフにN個の頂点がある場合、隣接行列のサイズはNxNになることを意味します。
Vがグラフの頂点のセットである場合、共通部分Mij隣接リスト= 1は、頂点iとjの間にエッジが存在することを意味します。
この概念をより明確に理解するために、無向グラフの隣接行列を準備しましょう。
上の図からわかるように、頂点Aの場合、AからBおよびAからEにエッジがあるため、交差ABとAEは1に設定されます。同様に、交差BAは無向であるため、1に設定されます。グラフおよびAB = BA。同様に、エッジがある他のすべての交差点を1に設定しました。
グラフが有向の場合、交点MijViからVjに向けられた明確なエッジがある場合にのみ1に設定されます。
これを次の図に示します。
上の図からわかるように、AからBへのエッジがあります。したがって、交差点ABは1に設定されますが、交差点BAは0に設定されます。これは、BからAに向けられたエッジがないためです。
頂点EとDについて考えてみます。EからD、およびDからEのエッジがあることがわかります。したがって、隣接行列でこれらの交差を両方とも1に設定しました。
次に、加重グラフに移ります。重み付きグラフでわかっているように、重みとも呼ばれる整数が各エッジに関連付けられています。この重みは、存在するエッジの隣接行列で表されます。この重みは、「1」ではなく、ある頂点から別の頂点へのエッジがある場合に指定されます。
この表現を以下に示します。
隣接リスト
グラフを本質的にシーケンシャルな隣接行列として表す代わりに、リンクされた表現を使用することもできます。このリンクされた表現は、隣接リストと呼ばれます。隣接リストはリンクリストに他ならず、リスト内の各ノードは頂点を表します。
2つの頂点の間にエッジが存在することは、最初の頂点から2番目の頂点へのポインタによって示されます。この隣接リストは、グラフの頂点ごとに維持されます。
特定のノードのすべての隣接ノードをトラバースすると、隣接リストの最後のノードの次のポインタフィールドにNULLが格納されます。
次に、隣接行列を表すために使用した上記のグラフを使用して、隣接リストを示します。
上の図は、無向グラフの隣接リストを示しています。各頂点またはノードに隣接リストがあることがわかります。
無向グラフの場合、隣接リストの全長は通常、エッジの数の2倍です。上のグラフでは、エッジの総数は6であり、すべての隣接リストの長さの合計または合計は12です。
次に、有向グラフの隣接リストを作成しましょう。
上の図からわかるように、有向グラフでは、グラフの隣接リストの全長はグラフのエッジの数に等しくなります。上のグラフには、9つのエッジがあり、このグラフの隣接リストの長さの合計= 9です。
ここで、次の加重有向グラフについて考えてみましょう。重み付きグラフの各エッジには、重みが関連付けられていることに注意してください。したがって、このグラフを隣接リストで表す場合、エッジの重みを示す新しいフィールドを各リストノードに追加する必要があります。
加重グラフの隣接リストを以下に示します。
上の図は、重み付きグラフとその隣接リストを示しています。各ノードの重みを示す隣接リストに新しいスペースがあることに注意してください。
Javaでのグラフの実装
次のプログラムは、Javaでのグラフの実装を示しています。ここでは、隣接リストを使用してグラフを表しています。
import java.util.*; //class to store edges of the weighted graph class Edge { int src, dest, weight; Edge(int src, int dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; } } // Graph class class Graph { // node of adjacency list static class Node { int value, weight; Node(int value, int weight) { this.value = value; this.weight = weight; } }; // define adjacency list List adj_list = new ArrayList(); //Graph Constructor public Graph(List edges) { // adjacency list memory allocation for (int i = 0; i 出力:
グラフ走査Java
データの存在を検索するなどの意味のあるアクションを実行するには、グラフをトラバースして、グラフの各頂点とエッジに少なくとも1回アクセスする必要があります。これは、グラフをトラバースするのに役立つ一連の命令に他ならないグラフアルゴリズムを使用して行われます。
Javaでグラフをトラバースするためにサポートされている2つのアルゴリズムがあります 。
- 深さ優先探索
- 幅優先探索
深さ優先走査
深さ優先探索(DFS)は、ツリーまたはグラフをトラバースするために使用される手法です。 DFS手法は、ルートノードから開始し、グラフの奥深くまで移動して、ルートノードの隣接ノードをトラバースします。 DFS手法では、探索する子がなくなるまで、ノードは深さ方向にトラバースされます。
リーフノード(子ノードがなくなる)に到達すると、DFSはバックトラックして他のノードから開始し、同様の方法でトラバーサルを実行します。 DFS手法では、スタックデータ構造を使用して、トラバースされるノードを格納します。
以下は、DFS手法のアルゴリズムです。
アルゴリズム
ステップ1:ルートノードから始めて、スタックに挿入します
ステップ2:スタックからアイテムをポップし、「訪問済み」リストに挿入します
ステップ3:「訪問済み」としてマークされた(または訪問済みリスト内の)ノードの場合、まだ訪問済みとしてマークされていないこのノードの隣接ノードをスタックに追加します。
ステップ4:スタックが空になるまで、ステップ2と3を繰り返します。
DFSテクニックのイラスト
次に、グラフの適切な例を使用して、DFS手法を説明します。
以下にグラフの例を示します。 探索されたノードを格納するためのスタックと、訪問されたノードを格納するためのリストを維持します。
まずAから始めて、訪問済みとしてマークし、訪問済みリストに追加します。次に、Aの隣接するすべてのノードを検討し、以下に示すようにこれらのノードをスタックにプッシュします。
次に、スタックからノード、つまりBをポップし、訪問済みとしてマークします。次に、それを「訪問済み」リストに追加します。これを以下に示します。
ここで、AとCであるBの隣接ノードについて考えます。このうち、Aはすでに訪問されています。したがって、無視します。次に、スタックからCをポップします。 Cを訪問済みとしてマークします。 Cの隣接ノード、つまりEがスタックに追加されます。
次に、スタックから次のノードEをポップし、訪問済みとしてマークします。ノードEの隣接ノードは、すでにアクセスされているCです。したがって、無視します。
これで、ノードDのみがスタックに残ります。したがって、訪問済みとしてマークします。その隣接ノードは、すでにアクセスされているAです。したがって、それをスタックに追加しません。
この時点で、スタックは空です。これは、指定されたグラフの深さ優先走査が完了したことを意味します。
訪問済みリストは、深さ優先手法を使用したトラバーサルの最終シーケンスを示します。上のグラフの最終的なDFSシーケンスは、A-> B-> C-> E-> Dです。
DFSの実装
import java.io.*; import java.util.*; //DFS Technique for undirected graph class Graph { private int Vertices; // No. of vertices // adjacency list declaration private LinkedList adj_list[]; // graph Constructor: to initialize adjacency lists as per no of vertices Graph(int v) { Vertices = v; adj_list = new LinkedList[v]; for (int i=0; i 出力:
DFSのアプリケーション
#1)グラフでサイクルを検出します。 DFSは、エッジに戻ることができる場合に、グラフ内のサイクルの検出を容易にします。
#2)経路探索: DFSの図ですでに見たように、任意の2つの頂点が与えられると、これら2つの頂点間のパスを見つけることができます。
#3)最小 スパニングツリーと最短パス: 重み付けされていないグラフでDFS手法を実行すると、最小スパニングツリーと短絡パスが得られます。
#4)トポロジカルソート: トポロジカルソートは、ジョブをスケジュールする必要がある場合に使用されます。さまざまな仕事の間に依存関係があります。トポロジカルソートを使用して、リンカー、命令スケジューラ、データのシリアル化などの間の依存関係を解決することもできます。
幅優先トラバーサル
幅優先(BFS)手法では、キューを使用してグラフのノードを格納します。 DFS手法とは異なり、BFSではグラフを幅方向にトラバースします。これは、グラフをレベルごとにトラバースすることを意味します。あるレベルですべての頂点またはノードを探索すると、次のレベルに進みます。
以下に示すのは、幅優先探索手法のアルゴリズムです。 。
アルゴリズム
BFS手法のアルゴリズムを見てみましょう。
BFS手法を実行する必要があるグラフGが与えられます。
- ステップ1: ルートノードから始めて、キューに挿入します。
- ステップ2: グラフ内のすべてのノードに対して手順3と4を繰り返します。
- ステップ3: ルートノードをキューから削除し、[訪問済み]リストに追加します。
- ステップ4: 次に、ルートノードの隣接するすべてのノードをキューに追加し、ノードごとに手順2〜4を繰り返します。[ENDOF LOOP]
- ステップ6: 出口
BFSのイラスト
以下に示すグラフの例を使用して、BFS手法を説明しましょう。 「Visited」という名前のリストとキューを維持していることに注意してください。わかりやすくするために、DFSの例で使用したのと同じグラフを使用します。
まず、ルート、つまりノードAから始めて、訪問先リストに追加します。ノードAの隣接するすべてのノード、つまりB、C、およびDがキューに追加されます。
次に、ノードBをキューから削除します。訪問済みリストに追加し、訪問済みとしてマークします。次に、キュー内のBの隣接ノードを探索します(Cはすでにキュー内にあります)。別の隣接ノードAはすでにアクセスされているため、無視します。
次に、ノードCをキューから削除し、訪問済みとしてマークします。訪問者リストにCを追加し、隣接するノードEをキューに追加します。
次に、キューからDを削除し、訪問済みとしてマークします。ノードDの隣接ノードAはすでにアクセスされているため、無視します。
したがって、ノードEのみがキューに含まれます。訪問済みとしてマークし、訪問済みリストに追加します。 Eの隣接ノードは、すでにアクセスされているCです。だからそれを無視してください。
この時点で、キューは空であり、訪問済みリストには、BFSトラバーサルの結果として取得したシーケンスが含まれています。シーケンスは、A-> B-> C-> D-> Eです。
BFSの実装
次のJavaプログラムは、BFS手法の実装を示しています。
import java.io.*; import java.util.*; //undirected graph represented using adjacency list. class Graph { private int Vertices; // No. of vertices private LinkedList adj_list[]; //Adjacency Lists // graph Constructor:number of vertices in graph are passed Graph(int v) { Vertices = v; adj_list = new LinkedList[v]; for (int i=0; i 出力:
BFSトラバーサルのアプリケーション
#1)ガベージコレクション: ガベージコレクションをコピーするためにガベージコレクション手法で使用されるアルゴリズムの1つは、「チェイニーのアルゴリズム」です。このアルゴリズムは、幅優先探索法を使用します。
#2)ネットワークでのブロードキャスト: ネットワーク内のあるポイントから別のポイントへのパケットのブロードキャストは、BFS技術を使用して行われます。
#3)GPSナビゲーション: GPSを使用してナビゲートしながら、BFS手法を使用して隣接ノードを見つけることができます。
#4)ソーシャルネットワーキングウェブサイト: BFS技術は、特定の人を取り巻く人々のネットワークを見つけるためにソーシャルネットワーキングWebサイトでも使用されます。
#5)重み付けされていないグラフの最短経路と最小全域木: 重み付けされていないグラフでは、BFS手法を使用して、最小スパニングツリーとノード間の最短パスを見つけることができます。
Javaグラフライブラリ
Javaでは、プログラマーが常にグラフをプログラムに実装することを義務付けているわけではありません。 Javaには、プログラムでグラフを利用するために直接使用できる多くの準備が整ったライブラリが用意されています。これらのライブラリには、グラフとそのさまざまな機能を最大限に活用するために必要なすべてのグラフAPI機能があります。
以下に、Javaのいくつかのグラフライブラリの簡単な紹介を示します。
#1)グーグルグアバ: Google Guavaは、単純なグラフ、ネットワーク、値グラフなどを含むグラフとアルゴリズムをサポートする豊富なライブラリを提供します。
#2)Apache Commons: Apache Commonsは、このグラフデータ構造を操作するアルゴリズムを持つグラフデータ構造コンポーネントとAPIを提供するApacheプロジェクトです。これらのコンポーネントは再利用可能です。
#3)JGraphT: JGraphTは、広く使用されているJavaグラフライブラリの1つです。単純なグラフ、有向グラフ、加重グラフなどを含むグラフデータ構造機能と、グラフデータ構造で機能するアルゴリズムおよびAPIを提供します。
#4)SourceForge JUNG: JUNGは「JavaUniversalNetwork / Graph」の略で、Javaフレームワークです。 JUNGは、グラフとして表現したいデータの分析、視覚化、およびモデリングのための拡張可能な言語を提供します。
JUNGは、分解、クラスタリング、最適化などのためのさまざまなアルゴリズムとルーチンも提供します。
よくある質問
Q#1)Javaのグラフとは何ですか?
回答: グラフのデータ構造は、主に接続されたデータを格納します。 例えば、 人のネットワークまたは都市のネットワーク。グラフのデータ構造は通常、頂点と呼ばれるノードまたはポイントで構成されます。各頂点は、エッジと呼ばれるリンクを使用して別の頂点に接続されます。
Q#2) グラフの種類は何ですか?
回答: さまざまな種類のグラフを以下に示します。
- 折れ線グラフ: 折れ線グラフは、時間に対する特定のプロパティの変化をプロットするために使用されます。
- 棒グラフ: 棒グラフは、さまざまな都市の人口、全国の識字率などのエンティティの数値を比較します。
これらの主なタイプとは別に、絵文字、ヒストグラム、面グラフ、散布図などの他のタイプもあります。
Q#3)連結グラフとは何ですか?
回答: 接続グラフは、すべての頂点が別の頂点に接続されているグラフです。したがって、接続されたグラフでは、他のすべての頂点からすべての頂点に到達できます。
Q#4) グラフの用途は何ですか?
回答: グラフはさまざまなアプリケーションで使用されます。グラフは、複雑なネットワークを表すために使用できます。グラフは、ソーシャルネットワーキングアプリケーションでも使用され、人々のネットワークを示したり、隣接する人々やつながりを見つけるなどのアプリケーションに使用されます。
グラフは、コンピュータサイエンスにおける計算の流れを示すために使用されます。
Q#5) グラフをどのように保存しますか?
回答:グラフをメモリに保存する方法は3つあります。
#1) ノードまたは頂点をオブジェクトとして、エッジをポインタとして保存できます。
#二) 行と列が頂点の数と同じである隣接行列としてグラフを保存することもできます。各行と列の交点は、エッジの有無を示します。非加重グラフでは、エッジの存在は1で示され、加重グラフでは、エッジの重みに置き換えられます。
#3) グラフを保存する最後のアプローチは、グラフの頂点またはノード間のエッジの隣接リストを使用することです。各ノードまたは頂点には、隣接リストがあります。
結論
このチュートリアルでは、Javaのグラフについて詳しく説明しました。さまざまなタイプのグラフ、グラフの実装、およびトラバーサル手法について検討しました。グラフは、ノード間の最短パスを見つけるために使用できます。
今後のチュートリアルでは、最短経路を見つけるいくつかの方法について説明することにより、グラフを引き続き調査します。
=> ここで簡単なJavaトレーニングシリーズに注意してください。
推奨読書