java - 隣接リストの Java 実装

Question

各ノードに整数値を持つ* m行列があり、無向グラフです。その隣接リストを作成したいと思います。それ、どうやったら出来るの？どんな助けでも大歓迎です。

Answer 1

隣接リストを作成するための簡単な実装を次に示します。問題によると:

それぞれ可変サイズの n 個の連結リストがあります。

最初に、整数のリンクされたリストの ArrayList を初期化します。

ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>();

次に、次のコードを繰り返して、リンクされたリストを追加します。

adj_list.add(new LinkedList<Integer>());

グラフを表すためにそれを使用している場合、リンクされたリストの数=頂点の数.したがって、上記の行をn(頂点の数)回繰り返す必要があります。

ここで、番号 3、4、5 を最初のリンク リストに追加するとします。次の手順を実行します。

adj_list.get(0).add(3);
adj_list.get(0).add(4);
adj_list.get(0).add(5);

これは単に、頂点 0 から 3,4,5 までのグラフにエッジがあることを意味します。

Answer 2

まず、あなたが言っていることを除いて、あなたの説明は隣接行列のようmですn。隣接行列は常に正方なので、 と仮定する必要がありm==nます。行列の要素はエッジの重みです。

グラフの隣接リスト表現は、(通常)adjペアのセットの配列です。セットには、有向辺がある場合、つまり、表されたグラフの頂点から重みのあるadj[i]ペアが含まれます。<j, w>i--w-->jijw

この定義では、n空の隣接セットから始めadj[i]て、行列要素を反復処理する必要があることは明らかですm[i][j] = w。これらのそれぞれについて に追加<j, w>しadj[i]ます。

このための Java コードは非常に簡単なので、ここでは記述しません。隣接リストで表されるグラフのタイプは、 のようなものArrayList<HashMap<Integer, Integer>> adjacenciesです。ペアは、ハッシュ テーブルに格納された<j,w> in adj[i]マッピングです。このような隣接関係を作成するコードは. j -> wadjacencies.get(i)adjacencies.get(i).put(j, w)

iこのメソッドを使用すると、ハッシュ テーブル内のキーを反復処理することによって に隣接する頂点を反復処理したり、 を使用して特定のエッジのadjacencies.get(i)重みを検索したり、すべての通常のグラフ操作を行うことができます。 i--w-->jw = adjacencies.get(i).get(j)