[リソース構造]Graph/Tree/BST

Graph

ノードを接続する幹線(Edge)を一緒に配置するデータ構造

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

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  daejeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}

console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

理解する必要があるグラフィック用語。

無方向図
全方位図

一方向図(有向図)
図

、一方向のみ

入場回数(入場回数)/出駅回数(出駅回数):1つの頂点(入駅幹線)と出駅(出駅幹線)に入る幹線が何本あるかを示す.

隣接

(隣接)
2つの頂点の間に直接の幹線がある場合、この2つの頂点は隣接する頂点です.

磁気リング(self-loop)
頂点から入る幹線が直接自分に入る場合は、自分のループを持つように表現されます.他の頂点を通らないのが特徴です.

サイクル(cycle):1つの頂点から出発し、その頂点に戻ります.

グラフィックの表示方法:隣接マトリクス&隣接リスト

隣接行列

隣接行列は頂点間の隣接を表す行列で,2次元配列を持つ.
Aの頂点とBの頂点がつながっていれば、1、つながっていなければ0で表される表のようなものになります.

Aの入場回数は1:A->C
[0][2] === 1

Bの入場回数は2つ:B->A、B->C
[1][0] === 1
[1][2] === 1

Cの入場回数は1:C->A
[2][0] === 1

りんせつひょう

隣接リストは、各頂点がどの頂点に隣接しているかをリスト形式で表示します.
各頂点には、自分に隣接する他の頂点を含むリストがあります.

どうしてAがCより先ですか.この順番は重要ですか?
:幹線の順序は重要ではありません.
優先度を処理する必要がある場合は、より適切なデータ構造(ex.queue,heap)を使用するのが合理的です.

Tree

グラフィックの様々な構造における一方向グラフィックの構造.1本の枝から周囲に伸びる形態.ノードデータ構造
ツリーは階層モデルです.

ツリーは、ルーティングノード

を有する.

本のノードは、0個以上のサブノード

を有する.

そのサブノードにも0個以上のサブノードがあり、これは繰り返し定義されている.

サブノードを持たないノードは木の葉と同じであり,葉ノードと呼ばれる.

高さと深さを測ることができます.

BST(Binary Search Tree)

バイナリツリー(binary tree):最大2つのサブノードを含むツリーをバイナリツリーとして定義します.
バイナリ検索ツリー(binary search tree):左側のすべての子供がルートまたは親より小さい値として定義され、右側のすべての子供がルートまたは親より大きい値フィーチャーを持つバイナリ検索ツリーです.

完全バイナリツリー:最後のレベルを除くすべてのノードが満たされなければならない.最後のレベルのノードはすべて満たされる必要はないが、左側は

で満たさなければならない.

完全バイナリツリー:各ノードに0個または2個のサブノード

がある

飽和バイナリツリー(Perfect binary tree):正のツリーであれば完全なツリーです.
すべてのリーフノードのレベルが同じで、すべてのレベルが塗りつぶされたツリー.