10月26日TIL/DataStructure Graph

11269 ワード
TIL datastructure Graph テキストリンク

グラフィック


グラフィックは、ノード(ノード、または頂点-頂点-)とノードを接続する幹線(edge)から構成されます.グラフィックは方向なしでよい.これは、幹線で接続された2つのノードが対称である可能性があることを意味する.一方,方向性(directed)を有する可能性があり,これは非対称関係を意味する.今回の印刷では、方向図がありません.

グラフィック用語


  • ノード(node) : 頂点(vertice)とも呼ばれ、通常ノードはデータを格納します.

  • 幹線(edge):リンク、arcsとも呼ばれ、ノード間の関係を表す

  • 隣接する頂点(隣接する頂点) : 幹線で接続された頂点.上図では、ノードAとノードBを隣接頂点と呼ぶことができる

  • 単純パス(simple-path):パスに重複する頂点はなく、同じ幹線を通るパスはありません.

  • 次(degree):図中の1つの頂点に隣接する頂点の数がありません.上の図Aの差は3です.

  • 入場回数(出局回数)/入場回数(入局回数) : 方向図で使用される用語
    入場回数 1つのノードから外に出る幹線の数で、
    インバウンド数 外部ノードからのルート数

    • グラフィックタイプ

  • 図は、ノード(または垂直)とエッジ(またはアーク)からなり、接続されたオブジェクト間の関係を表す資料構造であり、ネットワークモデルである.
  • の方向性により、無方向図と有方向図に分けられ、幹線に料金や重み付けを割り当てる重み付け図がある.
  • 無方向図:幹線の双方向移動により、頂点Aと頂点Bを接続する幹線は、例えば(A,B)対で表される.
  • 方向図:幹線に方向性がある.A→Bしか歩けない幹線はで表します.とは違います.
  • 重み付け図:幹線に費用または重み付けを割り当てる図であり、「ネットワーク」とも呼ばれる.

    • グラフィックの実装


    図形の表現方式は隣接行列と隣接リストの2つの方式に分けることができる.

    隣接リスト

  • ノードに接続されているノードのリストが表示されます.方向図、重み付け図が与えられると、接続の場合を隣接リストに出力することができる.
  • に接続された幹線の情報のみが格納され、O(E)の空間が要求され、空間効率は高いが、O(v)の時間が2つの頂点が接続されているかどうかを決定するために要求される.

    • 隣接行列

  • 隣接行列はノードの2次元配列である.無方向図に重みがない図は隣接行列で表すことができる.
  • はすべての頂点の接続の有無を記憶し、O(V 2)の空間が必要であり、空間効率は低いが、2つの頂点が互いに接続されているかどうかを決定するためにO(1)の時間が必要である.

    • グラフィックメソッド

  • .addNode():新しいノードを作成し、グラフに追加します.
  • .contains() : node.valueが存在するかどうかを確認しboolean値を出力します.
  • .removeNode():ノードを削除し、接続された幹線を削除します.
  • .addEdge():2つのノードを接続するために新しいedgeを作成します.
  • .haseEdge():ノードが相互に接続されているかどうかを確認してブール値を出力します.
  • .removeEdge():接続ノードのedgeを削除します.
  • .forEachNode():各ノードをグラフィックで呼び出す.

    • 「グラフィック」(Graph)メソッドの実装

    /* Undirected Graph */
class Graph {
  constructor() {
    /*
     *  ex)
     *    nodes = {
     *      0: [ 1, 2 ],
     *      1: [ 0 ],
     *      2: [ 0 ]
     *    }
     */
    this.nodes = {};
  }

  addNode(node) {
    //addNode(node) - 그래프에 노드를 추가합니다.
    this.nodes[node] = this.nodes[node] || [];
  }

  contains(node) {
    //contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.
    if(this.nodes[node]) {
      return true;
    }
    return false;
  }

  removeNode(node) {
    //removeNode(node) - 그래프에서 노드를 삭제합니다.
    if(!this.nodes[node]) {
      return undefined;
    } else {
      if(this.nodes[node].length !== 0) {
        for(let edge of this.nodes[node]) {
          this.removeEdge(node, edge);
        }
      }
      delete this.nodes[node];
      return this.nodes;
    }
  }

  hasEdge(fromNode, toNode) {
    //hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.
    for(let i of this.nodes[fromNode]) {
      if(i === toNode) {
        return true;
      }
    }
    return false;
  }

  addEdge(fromNode, toNode) {
    //addEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 추가합니다.
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

  removeEdge(fromNode, toNode) {
    //removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.
    delete this.nodes[fromNode].pop(toNode);
    delete this.nodes[toNode].pop(fromNode);
  }
}

module.exports = Graph;
    Python collections.counter
    20日目:BOMとDOM、window.onload()、addEventListener()js解答用