グラフィック

グラフは頂点(vertex,node)と幹線(edge)からなる資料構造にすぎない.
道路を結ぶ村を地図で示すことを考えてみましょう.
地図はグラフともいえる.
地図上では、どの村も頂点で、道路は幹線です.
幹線は(v1, v2)と同じペアとして定義され、v1、v2はグラフの頂点である.
幹線の方向の有無によって、무방향 그래프と방향 그래프に分けられます.
幹線上で頂点の順序を計算する図形を方向性図形と呼ぶ.
方向図では、矢印で幹線を表します.
この幹線は頂点間の流れを意味する.
方向性のない図形を無方向図形または図形と呼ぶ.

用語

Vertex(頂点)

図の各頂点を頂点またはノードと呼ぶ.位置の概念.

頂点はデータを格納します.

上図では、0、1、2に3つのノードが存在する.

Edge(幹線)
-位置の関係.

ノードとノードとの間の線を接続します.(link, branch)

上図には、幹線が3本存在する.

完全図(完全図)

図のすべての頂点間に直接接続された幹線の図が存在する.

n個の頂点を有する無方向図:幹線数がn*(n-1) / 2の場合、完全図.

n個の頂点を有する方向図:幹線数n*(n-1)の完全図.

サブチャート(ローカル図)

元の図形の一部を部分図形と呼ぶ.

部分図の頂点と幹線は、元の図の頂点と幹線の部分集合である.

G 2はG 1の一部のグラフである.

隣接(隣接)

無方向図では、頂点A、Bの間に幹線が存在する場合、頂点Aは頂点Bに隣接する.

イベント(付属)

無方向図では、頂点A、Bの間に幹線が存在する場合、幹線(A、B)は頂点A、Bに属する.

パス長(パス長)

経路を構成するための幹線数.

単純パス(単純パス)

パスに重複する頂点はありません.

サイクル(サイクル)

単純パスの始点と終点が同じパスです.(closed path)

度(回):図中の1つの頂点に隣接する頂点の数がありません.

インチ-度(入力回数):方向図の頂点への入力の幹線数.

出-度(入場回数):方向図の頂点から出る方向の幹線数.

特長

のグラフは、ネットワークモデルです.

オブジェクトとその関係は柔軟に理解できる.

2以上の経路があります.

ノード間では、双方向パスを無方向/方向から持つことができる.

本線の有無はグラフにより異なります.

サイクルまたは非サイクル.

巡回はDFSまたはBFSからなる.

ノードの概念はありません.

親-子関係の概念はありません.

グラフィックタイプ

むきず

無方向図の幹線は幹線双方向を通過することができる.

頂点Aと頂点Bを結ぶ幹線(A,B)は、頂点対で表される.

(A,B)は

(B,A)に等しい

Ex)双方向道路

方向図

幹線方向図

A->Bしか歩けない幹線をで表します.

は『B,A』

とは異なる

Ex)一方通行路

図面の接続

については、図中のすべての頂点ペアがなく、常にパスが存在します.

Exツリー:ループなしの接続図.

非接続グラフィック

無方向図では、特定の頂点ペア間にパスは存在しません.

サイクル

単純パスの始点と終点は同じです.

単純パス:パスに重複する頂点がない場合.

ノンループ図

サイクルのグラフはありません.

完全なグラフィック

図のすべての頂点が互いに接続された図.

無方向完全図
-頂点数:nは幹線数:n * (n-1) / 2

グラフィックの実装

グラフィック構造を表すのは幹線なので、実際の情報は幹線に格納されます.

1.隣接リスト

すべての頂点(ノード)を隣接リストに保存します.

図は、

の各頂点付近の頂点をリストで示す.

に隣接する各頂点の配列リストには、頂点をインデックスとして幹線が格納される.

リストは、空間を動的に割り当て、空間利用率が高いという利点を有する.

2つの頂点が接続されているかどうかを確認するには、配列よりも長い時間が必要です(O(n)).

の実装は配列に比べて困難である.

2.隣接行列

2つの頂点の間に幹線が存在するかどうかを示す要素を含む2 D配列.

頂点を接続するノードに、他のノードが隣接する頂点であれば、1または0を加えます.

if(간선 (i, j)가 그래프에 존재)
  matrix[i][j] = 1;
else
  matrix[i][j] = 0;

の実装は比較的簡単です.

配列にはグラフィック幹線情報が格納されているため、2つの頂点が接続されているかどうかをすばやく問い合わせることができます.( O(1) )

は、すべての幹線上のすべての幹線の情報を2次元配列に格納し、実施時にはO(n^2)時間の複雑さを有する.

は無条件に2次元配列を必要とするため、必要以上の空間を浪費する.
また

本線の情報は記憶されていない.

無方向図については、2次幹線情報が格納される.

図面内のナビゲーション

最初の頂点から、グラフィックに存在するすべてのノードにアクセスします.これをグラフィックブラウズと呼びます.
グラフィックブラウズの方法としては,深度優先ブラウズ(DFS)と幅優先ブラウズ(BFS)がある.

深度優先ナビゲーション

は広範囲の探索の前に深く探索する.

できるだけ

に深く入り込み、どこにも行けない場合は、前のノードに戻るようにグラフを巡回します.

は、すべてのノードにアクセスするために使用される.

BFSよりも簡単です.

は、単純な再帰呼び出しインプリメンテーションまたはスタックインプリメンテーションを使用する.

幅優先ナビゲーション

ルートノード(または他の任意のノード)から、まず隣接ノードを参照する方法.

は深く探索する前に広範な探索を行う.

2つのノード間の最短パスまたは任意のパスを探します.

は、一般にキューを使用して実装される.