Ch14. グラフィック

14-1. 図形の理解と種類
グラフの歴史と物語

「すべての橋を渡って、初めて出発した場所に戻ってもらえませんか?」
あり得ない.各頂点に接続されている幹線の数は偶数でなければならず、幹線を通って最初の出発点の頂点に戻ることはできません.

幹線:橋
頂点
図形の理解と種類
頂点(頂点):接続先となるオブジェクトまたは位置
幹線(edge):頂点間の接続
頂点と幹線で表されるデータ構造はグラフィックです

むきず
:接続関係に方向性のないグラフィック

有向図
:直線方向情報を含むグラフィック

完全なグラフィック
:各頂点を他のすべての頂点に接続するグラフィック
方向図の頂点数=無方向図の頂点数x 2

重み付けシェイプとローカルシェイプ

加重パターン
:メインラインに重み付け情報構成の図形を配置する

ローカルグラフィック
:円図形の頂点と幹線からなる図形

グラフィックの集合表示

無方向図

グラフィックGの頂点セット:V(G)

図形Gの幹線セット:E(G)

V(G1) = {A, B, C, D} E(G1) = {(A, B), (A, C), (A, D), (B, C), (C, D)}

V(G2) = {A, B, C, D} E(G2) = {(A, C), (A, D), (B, C)}

方向図

ex)頂点Aが頂点Cを指す幹線

V(G3) = {A, B, C, D} E(G3) = {, , }

V(G4) = {A, B, C, D} E(G4) = {, , }

グラフィックのADT
図面を作成して初期化する場合は、幹線方向を選択するか、重みに値を割り当てるかを選択できます.それだけでなく、頂点と幹線の挿入と削除はいつでも可能です.

void GraphInit(UALGraph * pg, int hv);

グラフの初期化を行います.

定数は

の2番目の因子で伝達される.

void GraphDestroy(UALGraph *pg);

グラフの初期化中に割り当てられたリソースが返されます.

void AddEdge(UALGraph * pg, int fromV, int toV);

パラメータfromVとtoVが伝達する接続頂点の幹線をグラフに追加します.

void ShowGraphEdgeInfo(UALGraph * pg);

グラフの幹線情報

を出力する.
頂点の名前付け
enum {A, B, C, D, E, F, G, H, I, J}

頂点名を定量化
ex)5が関数の2番目のパラメータとして伝達すると、頂点A,B,C,D,Eからなるパターン

が形成される.
グラフィックを実現する2つの方法

隣接行列に基づく図形:正方形行列を利用する
1)方向図なし

4つの

頂点、2つの横方向の長さ4の2次元アレイ宣言

2つの頂点接続

は1を表し、非接続は0は

を表す.

本線は方向性がないため、1本の幹線について2点を1と表記する
2)方位図

無方向図とは異なり、非対称

[0][1]の位置のみを1で示し、

AからBまでの幹線を示す.

隣接リストに基づくグラフィック:接続リストの使用
1)方向図なし

各頂点には、自分が接続している頂点の情報を含む接続リストがあります.

各頂点に接続された幹線の情報は、各接続リストにそれぞれ列挙されるべきである

2)方位図

は、各頂点が指す頂点の情報のみを含む、

.
増加ノード数は

の無方向図と比較して

に半減する.
14-2. 図面内のナビゲーション
深度優先探索(Depth Priority Search:DFS)

「緊急連絡網を見たら、ジミーとジローに連絡します.まず、ジミーだけに連絡しましょう.連絡があれば、ジローも連絡しますから」
一人だけの想い

深入浅出
「連絡してくれた人に連絡があったので、連絡してくれた人の中に連絡してくれた人がいるかどうか連絡してください!」

［DFSの完全プロセス］

人だけ連絡します.

誰も連絡していない場合は、自分に連絡した人に通知します.

最初に連絡を開始した人の位置で、連絡が終了します.

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

「一人でメッセージを送信する人数(幅)に応じて」

「東洙はまず周囲の人に連絡し、民錫は周囲の人に連絡する」.

深さ優先ナビゲーションの実装モデル

スタック:パス情報を追跡するための

配列:アクセス情報を記録するための

「東洙を離れてジミンを訪ねた時、離れた東洙の名前(情報)をスタックに移した」.

すべての人に連絡すると、スタックの中で連絡する人の情報を見つけることができます.

連絡するオブジェクトが見つかったら、スタックに再移行します.

幅優先ナビゲーションの実装モデル

キュー:アクセス数レコードを目的とします.

配列:アクセス情報を記録することを目的とする.

2人の連絡先の名前がキューに入り、キューから名前を取り出し、その名前の頂点に接続されているすべての人に接続します.

「頭がはっきりしている」という名前がQに入り、「頭がはっきりしている」と連絡のない相手まで「頭がはっきりしている」という名前が出てきます.
14-3. 最小コスト拡張ツリー
ループを形成しないグラフィック

頂点Bから頂点Dへのパス

B - A - D

B - C - D

B-A-C-Dが僅かに回転する経路

B-C-A-Dが僅かに回転する経路

単純パス
:同じ幹線を繰り返す経路を含まない
単純でないパスの例

B-A-C-B-A-D-BとAの2本の幹線
サイクル
:単純パス、開始パスと終了パスが同じ

ひろがりじゅ
:ループを形成しないグラフィック
最小コスト拡張ツリーの理解と適用
伸びた木の特徴

図のすべての頂点は幹線でつながっている

図内に周期

は形成する.
幹線に方向性を付与する方向図に対して伸長木を構成してもよい

最小コスト拡張ツリーまたは最小拡張ツリー
:幹線重み付けが最小の図形

[道路建設プロジェクト]
江原道(カンウォンド)、京畿道(キョンギド)、慶尚北道(キョンサンブクド)、蔚山(ウルサン)、全羅北道(チョンラブクド)を結ぶ物流に専用道路を建設する.

「5つの地域をつなぎ、距離を最小限に抑える形で道路を建設する」.

クルーズアルゴリズム1は、最小コストの拡張ツリーを構成するために使用されます.

Kruskalアルゴリズム
:重み付けで幹線をソートし、MSTになるまで幹線を選択または削除します.

Primアルゴリズム
:頂点からツリーを展開し、MSTになるまで

重み付け7の幹線を1本追加すると、図形内にループが形成されます

幹線の数+1=頂点の数

の重み付けを基準として、幹線

を昇順に並べる.

低重みの幹線からグラフに1つずつ追加

サイクルを形成する幹線は

を加えない.

間のシーケンス数が1つの定点数より少ない場合、MSTは

を完了する.
クルーズアルゴリズム2は、最小コストの拡張ツリーを構成するために使用される

重み付け8の幹線を削除すると、頂点Aと頂点Dはどの経路を通っても到達しません.
MSTの頂点はすべて幹線でつながっている

の重み付けを基準に、降順に幹線を並べます.

の重みの高い幹線から、グラフから1つずつ削除します.

の2つの頂点を接続する他のパスがない場合、幹線は削除されません.

幹線の数が頂点の数より少ない場合、MSTは完了する.