データ構造とアプリケーションにおけるグラフの種類

序章

グラフは、ノードとエッジで構成される非線形構造です。 これには、ノードのペアを接続するエッジによって保持されるノードの有限または無限のセットを含めることができます。 データ構造は、コーディングの概念の重要な部分です。 したがって、データ構造内のさまざまなタイプのグラフをしっかりと把握しておくと、複雑な実世界の問題を解決するのに役立ちます。

今日の世界では、データは力です。 したがって、簡単にアクセスできるようにデータを効率的に整理することは、どのプログラマーにとっても不可欠です。 データ構造とそのさまざまなグラフに関する知識は、コーディング スキルを強化して、現実世界の問題に的を絞り、そのソリューションを効果的に提供します。

データ サイエンスを学び、競合他社より優位に立つ

データ構造で一般的に使用されるさまざまなタイプのグラフと、それらが実際にどのように適用されるかを見てみましょう。

データ構造におけるグラフの種類

データ構造は、 Python グラフ データ構造や Java グラフ データ構造など、すべての言語の実用的なデータ ストレージ標準です。 データ構造の研究を目指す人にとって、すべてのタイプのグラフをマスターすることは最優先事項です。 グラフ理論には多くの実生活への応用があるため、データ構造において重要になります。

データ構造のさまざまなタイプのグラフを以下にリストできます。

1.ヌルグラフ

名前が示すように、null グラフは空です。 つまり、エッジのないグラフです。 空のエッジ セットを持つグラフ内の孤立した頂点のみで構成されます。

2.有限グラフ

グラフ内のエッジとノードの数が有限数である場合、そのグラフは有限グラフと呼ばれます。

3. 無限グラフ

グラフ内のノードの数とエッジの数に有限数を置くことができない場合、そのグラフは無限グラフとして知られています。 無限グラフは数えられません。つまり、このタイプのグラフのノードまたはエッジの数を数えることはできません。

4.単純なグラフ

頂点のペアの間にエッジが 1 つしかない場合、グラフは単純であると言われます。 したがって、2 つのノードはグラフ内の 1 つのエッジで接続され、それらの間の明確な関係を識別できます。

5.マルチグラフ

ノードのペアがグラフ内の複数のエッジで接続されている場合、そのグラフはマルチグラフと呼ばれます。 マルチグラフは自己ループで構成されていません。 マルチグラフに存在できるエッジには 2 種類あります。 彼らです：

• 平行エッジ

1 つのソースから同じ目的地に向かう 2 つの平行する道路のように、平行に走るエッジは、平行エッジと呼ばれます。

• ループ

これは、始点と終点の頂点が同じエッジです。

米国をチェック - データサイエンスプログラム

6.有向グラフ

2 つのノードまたは頂点の間に存在するすべてのエッジに定義された方向がある場合、グラフは有向であると言われます。 有向グラフは有向グラフとも呼ばれます。 有向グラフを見ることで、開始ノードと終了ノードを決定できます。 有向グラフと呼ばれるには、有向グラフのすべての辺が方向付けられている必要があることに注意してください。

7. 無向グラフ

エッジを見て開始ノードと終了ノードを特定するのが難しい場合、グラフは無向グラフであると言われます。 有向グラフと同様に、無向グラフと呼ばれるにはエッジが無向でなければなりません。

8. 接続されたグラフ

連結グラフは、すべてのノード間に少なくとも 1 つのパスが存在するグラフです。 簡単に言えば、接続されたグラフのノードから開始すると、グラフに存在するすべてのノードにアクセスできるはずです。 したがって、すべてのノードに少なくとも 1 つのパスが必要です。

9. 切断されたグラフ

このタイプのグラフでは、ノードまたは頂点のペアの間にエッジは存在しません。 したがって、接続されたグラフとは異なり、任意の頂点からすべてのノードに到達することはできません。 頂点のペア間にパスがない場合、それは切断されたグラフと呼ばれます。

10.完全なグラフ

グラフは、すべてのノード間にエッジが存在する場合にのみ完全であると見なされます。つまり、エッジがグラフ内のすべての頂点を接続します。 n 個の頂点の完全なグラフはKnで示され、グラフのエッジの数はnC2です。

11.循環グラフ

循環グラフと見なされるには、グラフに少なくとも 1 つの循環コンポーネントが必要です。 反対に、グラフにサイクルが含まれていない場合、非巡回グラフと見なされます。

12. 通常のグラフ

通常のグラフでは、すべての頂点が同じ次数を持つ必要があります。 ノードの次数は、それに接続されているノードの数として定義できます。 したがって、通常のグラフでは、すべてのノードが同じ数のノードに接続されている必要があります。

13. 二部グラフ

グラフが 2 部グラフであるためには、次の基準を満たす必要があります。

• グラフは頂点のセットに分割する必要があります。
• エッジは、1 つのグループのノード間から反対側にのみ形成する必要があります。 このルールは、同じノード セットの 2 つの頂点間の接続を防ぎます。
• 2 つのグループには、それらの間に共通の頂点があってはなりません。

上記のすべての規則に従うグラフは、二部グラフと見なされます。

14. ラベル付きグラフ

グラフのエッジに重みを付けることができます。 エッジに関連付けられた重みは、そのエッジを通過するコストとして理解できます。 これらの値は、固定パラメーターに基づくことができ、グラフ間で変化する可能性があります。 ここで、すべてのエッジがそれらに関連付けられた重みを保持している場合、そのグラフはラベル付きグラフと呼ばれます。

15.有向非巡回グラフ

有向非巡回グラフは、有向グラフと非巡回グラフの組み合わせであり、グラフの有向エッジが循環を形成しません。 反対に、有向巡回グラフは、循環を形成する有向エッジを持つグラフです。

データ構造におけるグラフの適用

コンピュータ サイエンスにおけるグラフの最も顕著な用途は、計算の流れの表現です。 グラフの他の有名な使用例は次のとおりです。

1. Google マップ

Google マップでは、グラフ データ構造が輸送システムを定義して計算します。 道路が別の道路と合流して交差点を形成する場合、それはノードと見なされ、そのような 2 つのノード間の道路はエッジとして扱われます。 したがって、Google マップは、グラフ データ構造を使用して、目的地までの最短かつ最速の方法を見つけます。

2.フェイスブック

Facebook は無向グラフを使用して、ユーザーとユーザーの友達を識別します。 すべてのユーザーが頂点として扱われ、それらを友人として結合する接続がネットワークの端になります。 グラフのデータ構造に基づくアルゴリズムを使用して、Facebook は「あなたが知っているかもしれない人」を提案し、「相互の友人」を表示します。

3.ワールドワイドウェブ

World Wide Web は、有向グラフの例です。 これは、Google ランキング システムの背後にある基本的な考え方でもあります。 World Wide Web システムでは、すべての Web サイトと Web アプリはノードまたは頂点として扱われ、ある Web サイトから別の Web サイトへのリンクはエッジと見なされます。

4.オペレーティングシステム

オペレーティング システムは、すべてのプロセスとリソースをノードまたは頂点として使用するリソース アロケーション グラフの一般的な使用例です。 エッジは、割り当てられたプロセスへのリソース間、または要求プロセスから要求されたリソースへのリソース間で発生します。 このサイクルが無限ループを形成し、デッドロックを初期化する場合があります。

5. マッピングシステム

GPS は、このテクノロジーを利用して検索することを選択した近くのレストラン、ショップ、および場所を特定するためによく使用されるグラフの例です。

6. マイクロソフト エクセル

有向非巡回グラフまたは DAG は、Microsoft Excel で使用されます。

7. ダイクストラ アルゴリズム

ダイクストラ アルゴリズムは、グラフ データ構造を使用して、2 つまたは場合によっては 3 つ以上のノード間の最短パスを識別します。

8.フライトネットワーク：

最適化された飛行ネットワークの計算は、グラフ データ構造のもう 1 つの実際のアプリケーションです。 空港をノード、ルートをエッジと考えると、データはグラフの基準に完全に適合します。 そのため、さまざまな強化されたアルゴリズムの助けを借りて、2 つの空港またはノード間の最適なルートが決定されます。

これらは、データ構造内のグラフのさまざまなアプリケーションであり、スムーズな機能を整理および維持するために、さまざまなアプリケーションやシステムで世界中で使用されています。

データサイエンティストとしての旅を始めましょう

データ サイエンティストになり、私たちが学んださまざまなグラフを使用してデータを巧みに処理したい場合は、upGrad の広範なデータ サイエンス コースをチェックしてください。 最も人気のあるコースの 1 つは、データ サイエンスの PG-IIITB コースです。これは、意欲的なデータ サイエンティストや新進気鋭のデータ サイエンティストが始めるのに最適なコースです。

コースの内容はこちら。

• 業界の専門家やメンターによる 360 度のキャリア サポート
• 業界プロジェクトの実践的な経験と、定期的な進捗状況を評価するための詳細なケース スタディ
• 世界中のすべてのセクターのデータ サイエンスの専門家とのネットワーキング

また、 Data Scienceで他のすべてのupGrad コースを確認することもできます。