隣接リストとは何か、プライオリティ キューとは何かについて、私は少し混乱しています。
Arraylist を使用して隣接リストを作成します。私が混乱しているのは、隣接リストに保持されているものです。
何が指されているかを示すために隣接リストが使用されていますか?
例、次のデータがあります。
u v weight
1 4 6
2 5 7
3 7 1
1 3 2
1 2 5
2 2 9
したがって、隣接リストの場合、次のようになります。
1 --->4---->3---->2
2 --->5---->2
3 --->7
同じ "u" (つまり、u 列の下に 3 つの 1 がある) は、対応する "v" を指します。
グラフ内のノードの隣接リストには、そのノードの隣接ノードがすべて表示されます。基本的に、隣接リストは、ノードが「自分から始めてこれらの他のノードに到達できる」または「ここに接続しているノードがある」と言う方法です。より具体的な例として、隣接する他の都市に通じる道路がある都市 (Graphville と呼びましょう) を想像するとします。次に、Graphville がノードで、Graphville から直接(つまり、他の都市を経由せずに) 到達できるすべての都市のリストは、Graphville の隣接リストにあります。
プライオリティ キューは、各要素に「優先度」が関連付けられている点を除いて、通常のキューに似たデータ構造です。通常、優先度の高い要素は優先度の低い要素よりも先に処理されます。
グラフ理論とコンピューター サイエンスでは、グラフの隣接リスト表現は、グラフの頂点ごとに 1 つずつ、順序付けられていないリストのコレクションです。各リストは、その頂点の近傍のセットを記述します。
ノードのネイバーを格納するだけであることを意味します。linkedListしたがって、近傍をまたはArrayまたはに格納できArrayListます。
プライオリティ キューは、通常のキューまたはスタック データ構造に似た抽象データ型ですが、さらに各要素に「優先度」が関連付けられています。プライオリティ キューでは、優先度の高い要素が優先度の低い要素の前に処理されます。2 つの要素の優先度が同じ場合、それらはキュー内の順序に従って処理されます。
JavaPriorityQueueでは、がありPriorityBlockingQueueます。
ウィキから