graph implementation c using adjacency list
このチュートリアルでは、C ++でのグラフの実装について説明します。また、グラフのさまざまなタイプ、表現、およびアプリケーションについても学習します。
グラフは非線形のデータ構造です。グラフは、2つ以上の頂点を接続する「頂点」および「エッジ」とも呼ばれるノードのコレクションとして定義できます。
グラフは、頂点が親子関係を持たないが、頂点間の複雑な関係を維持する循環ツリーとして見ることもできます。
データベースインタビューの質問と回答pdf
=> 絶対C ++トレーニングシリーズについては、ここをクリックしてください。
学習内容：
C ++のグラフとは何ですか？
上で述べたように、C ++のグラフは、頂点とエッジのコレクションとして定義された非線形データ構造です。
以下は、グラフのデータ構造の例です。
上記のグラフGの例を示します。グラフGは、頂点のセット{A、B、C、D、E}とエッジのセット{（A、B）、（B、C）、（A、D）、 （D、E）、（E、C）、（B、E）、（B、D）}。
グラフの種類–有向グラフと無向グラフ
エッジに方向がないグラフは、無向グラフと呼ばれます。上に示したグラフは無向グラフです。
エッジに方向が関連付けられているグラフは、有向グラフと呼ばれます。
以下に、有向グラフの例を示します。
上に示した有向グラフでは、エッジは順序対を形成し、各エッジは1つの頂点から別の頂点への特定のパスを表します。パスが開始する頂点は「 初期ノード パスが終了する頂点は「」と呼ばれます。 ターミナルノード 」。
したがって、上のグラフでは、頂点のセットは{A、B、C、D、E}であり、エッジのセットは{（A、B）、（A、D）、（B、C）、（B、E ）、（D、E）（E、C）}。
以下のグラフに関連して使用されるグラフの用語または一般的な用語について説明します。
グラフの用語
- バーテックス： グラフの各ノードは頂点と呼ばれます。上のグラフでは、A、B、C、およびDがグラフの頂点です。
- 縁： 2つの頂点間のリンクまたはパスは、エッジと呼ばれます。 2つ以上の頂点を接続します。上のグラフのさまざまなエッジは、AB、BC、AD、およびDCです。
- 隣接ノード： グラフでは、2つのノードがエッジで接続されている場合、それらは隣接ノードまたは隣接ノードと呼ばれます。上のグラフでは、頂点AとBがエッジABで接続されています。したがって、AとBは隣接するノードです。
- ノードの次数： 特定のノードに接続されているエッジの数は、ノードの次数と呼ばれます。上のグラフでは、ノードAの次数は2です。
- 道： グラフ内のある頂点から別の頂点に移動する必要があるときにたどる必要のあるノードのシーケンスは、パスと呼ばれます。グラフの例では、ノードAからCに移動する必要がある場合、パスはA-> B-> Cになります。
- 閉じたパス： 初期ノードが端末ノードと同じである場合、そのパスはクローズドパスと呼ばれます。
- 単純なパス： 他のすべてのノードが異なる閉じたパスは、単純パスと呼ばれます。
- サイクル： 繰り返されるエッジや頂点がなく、最初と最後の頂点が同じであるパスは、サイクルと呼ばれます。上のグラフでは、A-> B-> C-> D-> Aはサイクルです。
- 接続されたグラフ： 接続されたグラフは、各頂点の間にパスがあるグラフです。これは、分離された、または接続エッジのない単一の頂点がないことを意味します。上に示したグラフは接続されたグラフです。
- 完全グラフ： 各ノードが別のノードに接続されているグラフは、完全グラフと呼ばれます。 Nがグラフ内のノードの総数である場合、完全グラフにはN（N-1）/ 2個のエッジが含まれます。
- 加重グラフ： 各エッジに割り当てられた正の値は、その長さ（エッジで接続された頂点間の距離）を示し、重みと呼ばれます。重み付きエッジを含むグラフは、重み付きグラフと呼ばれます。エッジeの重みはw（e）で表され、エッジをトラバースするコストを示します。
- ダイアグラフ： 有向グラフは、すべてのエッジが特定の方向に関連付けられており、トラバーサルは指定された方向でのみ実行できるグラフです。
グラフ表現
グラフのデータ構造をメモリに保存する方法を「表現」と呼びます。グラフは、順次表現またはリンク表現として保存できます。
これらのタイプの両方を以下に説明します。
順次表現
グラフの順次表現では、隣接行列を使用します。隣接行列は、サイズn x nの行列です。ここで、nはグラフ内の頂点の数です。
隣接行列の行と列は、グラフの頂点を表します。頂点間にエッジが存在する場合、行列要素は1に設定されます。エッジが存在しない場合、要素は0に設定されます。
以下に、隣接行列を示すグラフの例を示します。
上のグラフの隣接行列を見てきました。これは無向グラフであり、エッジが両方向に存在すると言えることに注意してください。 例えば、 エッジABが存在するため、エッジBAも存在すると結論付けることができます。
隣接行列では、エッジが存在する場合は常に1に設定され、エッジが存在しない場合は0に設定される行列要素である頂点の相互作用を確認できます。
ここで、有向グラフの隣接行列を見てみましょう。
上に示したように、隣接行列の交差要素は、ある頂点から別の頂点に向けられたエッジがある場合にのみ1になります。
上のグラフでは、頂点Aから2つのエッジがあります。一方のエッジは頂点Bで終了し、もう一方のエッジは頂点Cで終了します。したがって、隣接行列では、AとBの交点はAとCの交点として1に設定されます。
次に、重み付きグラフの順次表現を確認します。
以下に、重み付きグラフとそれに対応する隣接行列を示します。
加重グラフの順次表現は、他のタイプのグラフとは異なることがわかります。ここで、隣接行列のゼロ以外の値は、エッジの実際の重みに置き換えられます。
エッジABの重みは4であるため、隣接行列では、AとBの共通部分を4に設定します。同様に、他のすべての非ゼロ値はそれぞれの重みに変更されます。
隣接リストは、実装と追跡が簡単です。トラバーサル、つまり、ある頂点から別の頂点にエッジがあるかどうかを確認するにはO（1）時間がかかり、エッジを削除するにはO（1）もかかります。
グラフがまばら（エッジが少ない）であろうと密であろうと、常により多くのスペースを必要とします。
リンクされた表現
グラフのリンクされた表現には隣接リストを使用します。隣接リスト表現は、グラフの各ノードと、このノードに隣接するノードへのリンクを維持します。隣接するすべてのノードをトラバースするとき、リストの最後で次のポインターをnullに設定します。
まず、無向グラフとその隣接リストについて考えてみましょう。
上に示したように、ノードごとにリンクリスト（隣接リスト）があります。頂点Aから、頂点B、C、およびDへのエッジがあります。したがって、これらのノードは、対応する隣接リストのノードAにリンクされています。
次に、有向グラフの隣接リストを作成します。
上記のグラフでは、頂点Eに由来するエッジがないことがわかります。したがって、頂点Eの隣接リストは空です。
次に、重み付きグラフの隣接リストを作成しましょう。
重み付きグラフの場合、上記のようにエッジの重みを示すために隣接リストノードにフィールドを追加します。
隣接リストに頂点を追加する方が簡単です。また、リンクリストの実装によりスペースを節約します。ある頂点と別の頂点の間にエッジがあるかどうかを調べる必要がある場合、操作は効率的ではありません。
グラフの基本操作
グラフのデータ構造に対して実行できる基本的な操作は次のとおりです。
- 頂点を追加します。 グラフに頂点を追加します。
- エッジを追加します。 グラフの2つの頂点の間にエッジを追加します。
- グラフの頂点を表示します。 グラフの頂点を表示します。
隣接リストを使用したC ++グラフの実装
次に、隣接リストを使用して単純なグラフを示すためのC ++実装を示します。
ここでは、重み付き有向グラフの隣接リストを表示します。隣接リストとグラフのエッジを保持するために2つの構造を使用しました。隣接リストは（start_vertex、end_vertex、weight）として表示されます。
C ++プログラムは次のとおりです。
#include using namespace std; // stores adjacency list items struct adjNode { int val, cost; adjNode* next; }; // structure to store edges struct graphEdge { int start_ver, end_ver, weight; }; class DiaGraph{ // insert new nodes into adjacency list from given graph adjNode* getAdjListNode(int value, int weight, adjNode* head) { adjNode* newNode = new adjNode; newNode->val = value; newNode->cost = weight; newNode->next = head; // point new node to current head return newNode; } int N; // number of nodes in the graph public: adjNode **head; //adjacency list as array of pointers // Constructor DiaGraph(graphEdge edges(), int n, int N) { // allocate new node head = new adjNode*(N)(); this->N = N; // initialize head pointer for all vertices for (int i = 0; i 出力：
出力：
グラフ隣接リスト
（start_vertex、end_vertex、weight）：
（0、2、4）（0、1、2）
（1、4、3）
（2、3、2）
（3、1、4）
（4、3、3）
トレントファイルをどのように開きますか
グラフの応用
グラフのいくつかのアプリケーションについて説明しましょう。
- グラフは、ネットワークグラフ、セマンティックグラフを表すため、または計算の流れを表すために、コンピュータサイエンスで広く使用されています。
- グラフは、プロセスへのリソースの割り当てを示したり、データフロー分析などを示すためにコンパイラで広く使用されています。
- グラフは、一部の特殊なコンパイラのデータベース言語でのクエリ最適化にも使用されます。
- ソーシャルネットワーキングサイトでは、グラフが人々のネットワークを表す主要な構造です。
- グラフは、輸送システム、特に道路網を構築するために広く使用されています。人気のある例は、世界中の方向を示すためにグラフを広範囲に使用するGoogleマップです。
結論
グラフは人気があり、広く使用されているデータ構造であり、他の分野とは別に、コンピュータサイエンスの分野自体で多くの用途があります。グラフは、2つ以上の頂点を接続する頂点とエッジで構成されます。
グラフは有向または無向にすることができます。線形表現である隣接行列と隣接リンクリストを使用してグラフを表すことができます。このチュートリアルでは、グラフの実装についても説明しました。
=> 完全なC ++チュートリアルリストについては、こちらをご覧ください。
推奨読書
