java - グラフ内の接続ノードのコーディング

Question

異なるノードを持つJavaでグラフを作成しようとしています。一部のノードは他のノードに接続され、一部は接続されません。それらが接続されている場合、そのノードのブール値が true になり、別の変数が接続先のノードの値を保持します。

...これにアプローチするための最良の方法は何だと思いますか?

Answer 1

グラフを表す最も一般的な 2 つの方法は、隣接行列と隣接リストです。n をノード数とします。

隣接行列 A はブール値の nxn 行列で、ノード i と j が接続されている場合は A(i, j) = 1、接続されていない場合は 0 となります。

各ノードの隣接リスト表現では、ノードが接続されている (隣接している) ノードのリストを維持します。

ここでの問題は、グラフで何をしたいかです。シンプルなものであれば、自分で巻いてみるのもいいかもしれません。そうでない場合は、グラフを処理するための Java ライブラリを Web で調べてみてください。 JGraphTについて言及されています。

隣接行列を使用する場合は、Java で bool または int の 2D 配列として簡単に表すことができます。各ノードにインデックスを付ける必要があります。これを行う最も簡単な方法は、常に同じ順序で Node オブジェクトを配列に保持することです。したがって、実際には 2 つのデータ構造があります。ノードの配列 (ノードが実際に何であるかを表すオブジェクト) と、インデックスによってノードを参照する隣接行列です。

マトリックスに入力すると、すべての列 (または行) の値 (0 と 1) を合計して最大値を見つけることで、他のほとんどのノードに接続されているノードを簡単に見つけることができます。お役に立てれば。

Answer 2

グラフを格納するための 2 つの標準モデルがあります。Tom が説明しているのはAdjacency Listです。もう 1 つは、スタンドアロンのAdjacency Matrixです。

効率を重視する場合は、状況のまばらさを調べてください (エッジが多いほど、行列バージョンの方がパフォーマンスに適しています)。パフォーマンスが問題にならない場合は、プログラムしたいものを使用してください...

Answer 3

クラスを作成し、Nodetype のインスタンス変数を与えますNode。null に初期化します。ノードが別のノードに接続されている場合、このインスタンス変数はそれを参照します。それ以外の場合、null のままになります。

ノードが多数のノードに接続されている可能性がある場合 (これはグラフでは非常に一般的です)、 を使用しArrayListて、そのノードが接続されているすべてのノードを格納します。

Answer 4

おそらく「Good Java Graph Algorithm Library? 」の複製です。'。簡単な答えは、JGraphTを見ることです。