Graph

グラフは簡単に言えば頂点と幹線の集合です.以前認識した木もグラフです.しかし、木は循環の形成を許さない.

グラフィック用語

Vertex & Edge

Vertexは頂点を意味します.頂点にはいくつかの値があります.

Edgeは幹線を表します.幹線は頂点と頂点を接続します.

Undirected Graph & Directed Graph

Undirected Graph

その名の通り、頂点と幹線の接続に方向性のないグラフです.

V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex # u와 vertex v를 연결하는 edge

Directed Graph

名前の通り、頂点と幹線の接続に方向性を持つグラフです.

V = {1, 2, 3, 4, 5, 6}
E = {(1, 4), (2,1), (3, 4), (3, 4), (5, 6)}
(u, v) = vertex # u에서 vertex v로 가는 edge

Degree

Undirected GraphのDegreeは、頂点と頂点を結ぶ幹線数を表します.

ガイドパターンでは、幹線方向性があるため、2つの部分に分けられる.各頂点から出る幹線の個数をOutdegree、各頂点に入る幹線の個数をIndegreeと呼ぶ.

重み付きグラフィック(Weight Graph)とローカルグラフィック(SubGraph)

加重パターン

重み付け図は、幹線に重み付けを加えた構成の図です.幹線を渡るときは重みを計算します.通常、「最小コストで目的地に到着する」などの問題に使用されます.

重み付けされていないグラフィック

非重み付け図はその名の通り幹線に重み付けがない図です.すべての幹線の周易度が同じパターンも存在する.

ローカルグラフィック

これは、グラフに適用される部分集合に似た概念です.元の図形の一部の頂点と一部の幹線からなる図形を指す.

グラフィックの表示

隣接行列

正方形マトリクスを用いてグラフィックを表す方法では,対応する位置のvalue値により,頂点間の接続関係がO(1)の時間的複雑さで理解できる.頂点個数に関係なく、O(V(頂点)^2)の空間的複雑さがある.密な図形(密な図形:幹線の数が多い図形)を表現するのに適しています.(スペースの複雑さが高いので)

隣接リスト

各頂点の隣接リストを表示するには、接続リストを使用してグラフィックを表す方法が必要なため、頂点間の接続を確認するには時間がかかります.空間的複雑度はO(E＋V)であった.疎図形を表すのに適しています.(幹線の数が空間的複雑さに反映されるため)

図面内のナビゲーション

図形は頂点の構成だけでなく,幹線の接続にも特定の規則がないため,ナビゲーションが複雑である.図面内のすべての頂点を参照するには、次の方法を使用します.

深度優先ナビゲーション(DFS:Depth First Search)

グラフィックで、接続された頂点を任意の頂点から優先的に検索する方法.接続可能な頂点があるまで接続を続け、再接続可能な頂点がない場合は、すぐに前のステップに戻り、接続可能な頂点を参照します.深度優先探索にはStackを用いて実現する.時間的複雑度はO(V＋E)であった.(V:Vertex(頂点)、E:Edge(幹線)

幅優先ナビゲーション(BFS:Breadth First Search)

これは、任意の頂点から接続されたすべての頂点をグラフィックで優先的に検索する方法です.同じレベルの頂点をツリーで優先的に検索するようにします.Queueを使用して、頂点の順序を記録します.参照を開始する頂点は、Queueのenqueue、dequeue、およびdequeueの頂点に関連付けられた頂点です.これは、頂点をアクセス順にQueueに格納する方法です.時間的複雑度はO(V＋E)であった.(V:Vertex(頂点)、E:Edge(幹線)BFS로부터 도출된 경로는 최단 경로를 보장한다.

最小拡張ツリー(MST:Minimum生成ツリー)

Spanning Tree

グラフィック内のすべての頂点を含むツリーは、グラフィックの最小接続部分のグラフィックです.n個の頂点を有する図の最小幹線個数はn−1であり、n−1個の幹線を有する局所図は必然的にツリーの形式を有する.この木は新疆の木です.簡単に言えば、グラフの中でいくつかの幹線で作られた木が選択されていると言えます.

ツリーフィーチャーの生成

DFSにより、BFSはグラフ内に伸長ツリーを見つけることができる.(ナビゲーション中に使用する幹線を収集するだけで作成可能)

1の図には、複数の伸長ツリーが存在してもよい.

伸長ツリーは、周期を含まないすべての頂点が接続されたツリーの特殊な形式です.(ループが含まれている場合は、ツリーではありません.)

身長木はグラフのn個の頂点をn-1本の幹線に接続する.

Minimum Spanning Tree

これは、生成ツリーで使用される幹線重み付けと最小の生成ツリーを意味する.各幹線の重みが等しくない場合,単純に重みの最小の幹線を用いてMSTになるわけではない.幹線の重み付けを考慮して、最小費用の生成ツリーを選択します.

Minumum生成ツリーのプロパティ

幹線の重み付けと最小.

n個の頂点を持つグラフィックでは、n-1本の幹線のみを使用する必要があります.

サイクルは含まれません.

Minimum生成ツリーの実装

Kruskal Algorithm

これはGreedy法を用いてネットワークのすべての頂点を最小費用で接続する最適な解法である.初期化操作により、幹線がない場合は頂点のみで図形を構成し、その後、幹線を重み付け昇順に並べます.次に、整列した幹線の中から周期を形成しない幹線を選択し、順次追加します.生成ツリーが完了すると、すべての頂点が接続状態で終了し、完了できない図形については、すべての幹線を判断して終了します.
ループを作成するかどうか
グラフィックの各頂点にset-idという値を追加します.初期化プロセスでは、各頂点を1～nの値で初期化します.ここで、0は幹線に接続されていないことを意味します.そして接続するたびにset-idを1つに統一します.値を同じset-id個数のset-id値に統一します.
時間の複雑さ
幹線重み付けの昇順に並べる->O(E log E)
ループを作成しset-id->O(E+V logV)を統一するかどうかを確認します
全時間複雑度->O(E log E)

Prim Algorithm

初期化中の頂点からなる初期図A.Aの頂点と外部の頂点との間の幹線を接続することにより、最小重み付けされた幹線で接続された頂点を追加する.頂点に関係なく、幹線の重み付け値を基準に接続されます.このように接続された頂点がAに追加され、この手順を繰り返して生成ツリーが作成されます.簡単に言えば、これが前の段階で作成された伸び木の拡張方法です.ツリーの幹線がn-1本の場合、このプロセスは終了します.
時間の複雑さ
全時間複雑度->O(E logV)