グラフのデータ構造の概要はこちらからご覧ください...

このブログは、漠然としたやり方ではなく、コンセプトの要点を理解したい開発者を対象としています。この記事ではグラフのデータ構造を理解します。始めましょう。

グラフとは何ですか?

グラフは、エッジとノードという 2 つのコンポーネントを持つ非線形データ構造です。

ノードは: -

1. グラフの基本単位
2. 頂点または頂点とも呼ばれます。
3. はラベルを付けることも、ラベルを付けないこともできます。

エッジは:-

1. 2 つのノード間の接続
2. アークとも呼ばれ、
3. はラベルを付けることも、ラベルを付けないこともできます。

グラフの種類: -

1. ヌル グラフ: エッジがありません。
2. Trival グラフ: ノードが 1 つだけあります。
3. 循環グラフ: 少なくとも 1 つのサイクルが含まれます。
4. サイクルグラフ: すべてのノードが接続されて 1 つのサイクルを形成します。
5. 有向グラフ: そのエッジには方向があります。
6. 無向グラフ: そのエッジには方向がありません。
7. 加重グラフ: 各エッジに何らかの値が割り当てられます、
8. 接続されたグラフ: 1 つのノードから他のノードにアクセスできます (一意のエッジである必要はありません)。
9. 未接続のグラフ: 少なくとも 1 つのノードがノードから切断されています。
10. 通常のグラフ: すべての頂点には同じ数の近傍があります。
11. 完全なグラフ: すべてのノードは一意のエッジによって別のノードに接続されています
12. 有向非巡回グラフ: 循環のない有向グラフ
13. 二部グラフ: そのノードは、セット間にエッジが存在しないように 2 つのセットに分割できます。

グラフをどのように保存するのでしょうか?

方法は 2 つあります:

1. 隣接行列、および
2. 隣接行列

隣接行列は、グラフのデータ構造を表す 2 次元行列です。行と列はノードを表し、行列の値はエッジを表します。

上の画像では、4 つのノードがエッジで接続されています。ノード A はすべてのノードに接続されているため、A (行または列) が他のノードの行または列と交差するセルに値が 1 として追加されます。ノード B はノード A にのみ接続されており、ノード B がノード A と交差するセルの値は 1 になり、他のセルの値は 0 になります。

隣接する行列のエッジを追加または削除するための時間計算量は O(1) です。次の場合に使用できます: -

1. グラフには可能な最大のエッジがあります。
2. メモリの制約はありません。
3. グラフは複雑な構造をしています。

隣接リスト は、複数のリンクされたリストまたは配列を使用してグラフを保存しています。行はノードを表し (下の画像を確認してください)、行に存在する値は隣接ノードを表します。

上の画像には 5 つのノードがあります。ノード A はノード B とノード D に接続されているため、最初の配列にはこれらの値が含まれています。同様に、ノード B はノード A、ノード C、ノード D、およびノー​​ド E に接続されているため、2 番目の配列にはこれらのノードが含まれます。

エッジの取得または削除の時間計算量は O(n)、エッジの追加の時間計算量は O(1) です。隣接リストは次の場合に使用できます: -

1. ノードのエッジが少なくなります。
2. メモリの制約があり、
3. グラフはそれほど複雑ではありません。

図: 隣接するリストと隣接する行列の視覚的な比較。

グラフの使用例

グラフ データ構造の一般的な例の 1 つは次のとおりです。サッカーの分野では、各プレーヤーはノードと見なされ、それらの相互作用はエッジを表します。

グラフは、次のような前の例と同様のシナリオで使用されます。 -

1. 誰もがノードとなるソーシャルネットワークでは、
2. PC とルーターがノードとなるコンピューター ネットワークでは、
3. 交通網などで...

以上がグラフのデータ構造の概要はこちらからご覧ください...の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。