Graph

複数のポイント間の複雑な関連を表すデータ構造.
異なる点に直接的な関係がある場合、直接接続された線が存在し、間接的な関係がある場合、異なる点によって接続された線が存在する可能性があります.
ここで、点はグラフィックで頂点(頂点)として、線は幹線(エッジ)として表されます.

Graphの実際の使用例

ポータルサイトの乾色エンジン、SNS、Nationなどで使われる資料構造がグラフです.

頂点:ソウル、大田、釜山

本線:ソウル-大田、大田-釜山、釜山-ソウル
重み付けされていない(接続強度)現在のグラフィックを非重み付けグラフィックと呼びます.
簡単なJavaScriptオブジェクト

を使用して比較

let isConnected = {
  seoul: {
    busan: true,
    daejeon: true
  },
  dajeon: {
    seoul: true,
    busan: true
  },
  busan: {
    seoul: true,
    daejeon: true
  }
}
console.log(isConnected.seoul.daejeon) // true
console.log(isConnected.daejeon.busan) // true

非重み付け図は、各頂点間の接続の有無のみを判断し、重み付け図はより詳細な情報を含んでもよい.

頂点:ソウル、大田、釜山

幹線:ソウル-140キロ-大田、大田-200キロ-釜山、釜山-325キロ-ソウル
この重み付け図は、ナビゲーションで使用される資料構造と類似するために、数百万の頂点(アドレス)に拡張されます.

理解する必要がある用語。

無方向図:前述のナビゲーション例は無方向図である.ソウルから釜山まで、逆も同じだ.
しかし一方向図で示すとソウルから釜山に行くことは可能ですが、釜山からソウルに行くことは不可能です.(または反対の場合)
2つの場所が一般通路に接続されている場合は、一方通行幹線で表現できます.

入場回数(in-dgree)/入場回数(out-dere):頂点(入る幹線)と入場(出る幹線)に入る幹線が何本あるかを示します.

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

磁気回路(self-loop):頂点から入る幹線が直接自分に入ると、磁気回路があることを示します.他の頂点を通らないのが特徴です.

サイクル(cycle):1つの頂点から出発し、再び頂点に戻ることができる場合は、1つのサイクルがあることを示します.ナビゲーション例では、ソウル→大田→釜山→ソウルに移動できるため、自転車が存在する.

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

隣接行列

2つの頂点を直接接続する幹線がある場合は、この2つの頂点が隣接していると呼ばれます.
隣接行列は頂点間の隣接を表す行列で,2次元配列を持つ.
Aの頂点とBの頂点が連結されている場合は1であり、連結されていない場合は0を表す表である.
重み付けされたグラフィックの場合、関係に意味のある値(上記のナビゲーション例との距離)が格納され、1ではありません.
上の図を隣接行列として表します.

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

隣接行列はいつ使えばいいですか?

は、大きなテーブルと同じ隣接行列であり、2つの頂点間に関係があるかどうかを容易に決定することができる.

例えば、AからBまでの幹線が存在するか否かを判定するために、0行目の第1列にどのような値が格納されているかを直接判定することができる.主に

の最速パス(最短パス)を探すために使用されます.

りんせつひょう

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

BにはAとCに通じる幹線が2本あるのに、どうしてAがCより先なのですか.順番は重要ですか?

は一般的に重要ではないと言える.

優先度を処理する必要がある場合は、より適切なデータ構造(ex.queue,heap)を使用することが合理的である.したがって、一般的には重要ではありません.

隣接表はいつ使えばいいですか？

隣接行列は、すべての接続可能な状況の数を格納する.

が隣接していない場合は0が格納され、隣接している場合は1が格納されるため、大量のメモリが消費される.

メモリを効率的に使用するには、隣接マトリクスではなく隣接テーブルを使用します.

グラフィック実装

class GraphWithAdjacencyMatrix {
  constructor() {
    this.matrix = [];
  }
  addVertex() { // 그래프에 버텍스를 추가
    const currentLength = this.matrix.length;
    for(let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    }
    this.matrix.push(new Array(currentLength + 1).fill(0));
  }
  contains(vertex) { // 그래프에 해당 버텍스가 존재하는지 여부를 Boolean으로 반환
    if(this.matrix[vertex]) {
      return true;
    } else {
      return false;
    }
  }
  addEdge(from, to) { // fromVertex 와 toVertex 사이의 간선을 추가
    const currentLength = this.matrix.length;
    if(from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다");
      return;
    }
    // 간선을 추가할 수 없는 상황에서는 추가하지 말아야한다.
    if(from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다");
      return;
    }
    // 간선을 추가해야한다.
    this.matrix[from][to] = 1
  }
  hasEdge(from, to) { // 두 버텍스 사이에 간선이 있는지 확인
    if(this.matrix[from][to] === 1) {
      return true;
    } else {
      return false;
    }
  }
  removeEdge(from, to) {
    const currentLength = this.matrix.length;
    if(from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // 간선을 지울 수 없는 상황에서는 지우지 말아야 한다.
    if(from + 1 > currentLength || to + 1 > currentLength || from < 0 || to < 0) {
      console.log("범위가 매트릭스 밖에 있습니다.")
      return;
    }
    // 간선을 지워야 한다.
    this.matrix[from][to] = 0;
  }
}

Tree

図の様々な構造のうち、細い方向図の構造で、その形状が木に似ていることから木構造と名付けられた.
木の枝が1本から周りに伸びているからです.

このツリー構造をファミリーマップに近似して定義すると、次の1つ以上のデータにデータを一方向に接続する階層化されたデータ構造と呼ぶことができます.
データは順番に並べられた線形構造ではなく、1つのデータの背後に複数のデータが存在する可能性のある非線形構造であり、階層化されており、下にしか伸びていないため、ループはありません.

ツリー構造はルート(Root)と呼ばれる頂点データから始まり、複数のデータを1本の幹線(edge)に接続します.
これらのデータはノード(node)と呼ばれ、親ノードが子ノードに接続されている場合、親ノード/子ノード関係があります.
AはBとCの親ノードである.
BとCはAのサブノードである.
サブノードが木に等しい葉はなく、葉ノードと呼ばれます.

この資料構造は特に高さと深さを測定できる.
ノードとノード間の距離(距離)をレベル(Level)と呼び、最初のノードのルートとしてLevel 1を設定します.
ルートノードから一番奥のノードまでのレベルをツリーの高さ(Height)と呼び,逆に特定のノードからルートノードまでのレベルをノードの深さ(Depth)と呼ぶ.
同じレベルで並べられたノードは兄弟ノードで表される.
根から伸びる大きな木の内部に、木の形をした小さな木を子木といいます.(D-H-I, B-D-E, C-F-G-J)

ツリーの実際の使用例

最も代表的なのは,コンピュータのディレクトリ構造を考慮できることである.
いずれも1つのフォルダから始まり、枝状に伸びています.
ファイルシステムなどのすべてのインプリメンテーションは、ユーザーが使用できるようにツリーを使用して作成されます.

ツリー実装

class Tree { 
  constructor(value) { // constructor로 만든 객체는 트리의 Node가 된다.
    this.value = value;
    this.children = [];
  }
  insertNode(value) { // 트리의 삽입 메서드
    // 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요하다.
    const childNode = new Tree(value);
    this.children.push(childNode);
  }
  contains(value) { // 값이 포함되어 있다면 true를 반환
    if(this.value === value) {
      return true;
    }
    // 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색
    for(let i = 0; i < this.children.length; i++) {
      if(this.children[i].contains(value)) {
        return true;
      }
    }
    return false;
  }
}

BST(Binary Search Tree)

木は便利な構造を示すほか,効率的な探索にも用いられる.
最も簡単でよく使われるツリーは、バイナリツリー(binary tree)とバイナリ検索ツリー(binary search tree)です.
サブノードは、最大2つのノードからなるツリーをバイナリツリーとして定義します.
この2つのノードは、左サブノードと右サブノードに分けられます.
データの挿入,削除方式により,バイナリツリーは完全バイナリツリー,完全バイナリツリー,飽和バイナリツリーに分けられる.

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

正バイナリツリー:各ノードに0個または2個のサブノードがあります.

飽和バイナリ:正バイナリツリーで、完全バイナリツリーです.すべてのリーフノードのレベルは同じで、すべてのレベルが埋め込まれたツリーです.

すべての左側の子供はルートまたは親より小さい値であり、すべての右側の子供はルートまたは親より大きい特徴を持つバイナリツリーとして定義されます.
バイナリ・ナビゲーション・ツリーがバランシング・ツリーでない場合、入力した値がノードに順番に集約される場合があります.
これらの問題を解決するために,挿入と削除のたびにツリーの構造を再調整するアルゴリズムを導入することができる.