Graph

1)定義

:あるデータまたは概念の頂点を表す集合Vと、それらを接続する幹線の集合Eとからなるデータ構造

2）例

SNSでは、人との関係やナビなど頂点が多く、相互関係の頂点は一直線です.

3）理解すべき用語

-頂点(頂点):位置の概念.(nodeとも呼ばれる)
-幹線(edge):位置の関係.ノードを接続する直線(リンク、ブランチとも呼ばれる)
-隣接頂点(隣接頂点):幹線で直接接続された頂点
-頂点の数(度数):図の頂点に隣接する頂点の数がありません
無方向図に存在する頂点の全回数の和=図中の幹線数の2倍
-送り回数(in degree):方向図の外部からの幹線数(内差数とも呼ばれる)
-入場回数(out-dere):方向図から外への幹線数(外差数とも呼ばれる)
-方向図中の頂点の送り回数または送り回数の和=方向図中の幹線数(内差+外差)
-パス長(pathlength):パスを構成するための幹線数
-単純パス(simplepath):パスに重複する頂点がない場合
-サイクル(cycle):単純パスの始点と終点は同じです.

4）特性

-グラフはネットワークモデルです.
-2つ以上のパスがあります.
-つまり、ノード間に方向/方向の双方向パスがあるかどうか.
-self-loopだけでなく、loop/回路も可能です.
-ルートノードの概念がありません.
-親がいない-子供関係の概念.
−巡回はDFSまたはBFSからなる.
-グラフは循環または非循環です.
-グラフには主に方向図と無方向図があります.
-幹線の有無はグラフによって異なります.

5)タイプ

(1)方向図:新しい属性を持つ図で、各幹線を方向と呼ぶ
(2)無方向図:幹線無方向図
(3)重み付けパターン:各幹線に重み付けと呼ばれる実数属性を付与するパターン
(4)複数の図形:2つの頂点の間に2つ以上の幹線の図形を持つことができる
(5)単純なグラフィック:2つの頂点の間に最大1本の直線しかないグラフィック
(6)二分図:図形の頂点を重ならない二つの図形

6）実施

(1)隣接行列
:隣接行列はNxNブール行列であり、行列[i][j]がtrueであればi->jまでの幹線を表す.

class UndirectedGraph {
  constructor() {
    this.edges = {};
  }
  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = {}; // 객체에서 []를 쓰면 그게 키(key)라는 얘기
  }

  // 간선 추가하기
  addEdge(vertex1, vertex2, weight) {
    if (weight === undefined) {
      weight = 0;
    }
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
  }

  // 간선 삭제하기
  removeEdge(vertex1, vertex2) {
    if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
      delete this.edges[vertex1][vertex2];
    }
    if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
      delete this.edges[vertex2][vertex1];
    }
  }
  // 정점 삭제하기
  removeVertex(vertex) {
    for (let adjacentVertex in this.edges[vertex]) {
      this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
  }
}

(2)隣接表
:すべての頂点(またはノード)を隣接リストに保存します.すなわち,各頂点の隣接頂点はリストで表される.