[Data Structure] Graph

9944 ワード
JavaScript テキストリンク
図形はノード(Node,vertex)とノードを接続する幹線(edge)からなる.
グラフィックは方向性がない可能性があります.これは、幹線で接続された2つのノードが対称である可能性があることを意味する.一方,方向性を有する可能性があり,これは非対称関係を意味する.
  • 深度優先ナビゲーション
    ルートノードから複数のブランチに移動する前に、ブランチを完全にナビゲートします.
    広範な探索を行う前に,まず深い探索を行う.
  • 幅優先ナビゲーション
    ルートノードから、まず隣接ノードを参照します.
    すなわち,深さ(deep)探索を行う前に,広さ(wide)探索を先に行う.
  • のグラフは、ネットワークモデルです.
  • 2以上の経路があります.
    すなわち,ノード間には方向/方向の双方向経路の有無が考えられる.
  • self-loopだけでなく、loop/回路も可能です.
  • ノードの概念はありません.
  • 親-子関係の概念はありません.
  • 巡回はDFSまたはBFSからなる.
  • 図は、ループ図または非ループ図である.
  • 図は主に方向図と無方向図がある.
  • 本線の有無はグラフにより異なります.

    • 2つのグラフィック実装

  • 隣接表
    隣接テーブルで図形を表すのが最も一般的な方法です.
  • 入力マトリクス
    隣接行列は行列式で表される.
    • 今から実施しましょう.
  • addNode(ノード)-ノードをグラフィックに追加します.
  • addEdge(ノードからノードへ)-ノードからノードまでの幹線を追加します.
  • リモートノード(Node)-図面からノードを削除します.
  • 「ノードからノードへ」-ノードからノードまでの幹線を削除します.
  • haseEdge(FromNode,to Node)-FromNodeとTo Nodeの間に幹線が存在するかどうかを返します.
  • contains(node)-ノードがグラフィックに存在するかどうかを返します.
    • class Graph {
  constructor() {
    /*{"nodes":
	{"1": [], 
	"2": [3], 
	"3": [2]}}
  */
    this.nodes = {};
  }
    ノードを追加します.
    addNode(node) {// 그래프에 노드 추가
    this.nodes[node] = [];
    //노드가 추가 되면 키와 빈배열 추가  
  }
    ノードを確認します.
    contains(node){
  reutrn this.nodes[node].hasOwnProperty(node);
  //hasOwnProperty는 키있는지 확인하고 t/f리턴
}
    ノードを削除します.
    removeNode(node){
if(this.nodes[node].length === 0){
	delete this.nodes[node];
  //엣지가 없는 노드라면 노드만 삭제
}else{
	for(let el of this.node[node]){
    	this.removeEdge(node,el);
      //엣지가 있다면 엣지도 순환 하며 엣지도 삭제 
        }
	}
}
    画像を追加します.
    hasEdge(fromNode,toNode){
for(let el of this.nodes[node]){
	if(el === toNode){
      return ture;
    }
}
  return false;
}
    画像を追加します.
    addEdge(fromNode, toNode) {// fromNode와 toNode 사이의 간선을 추가합니다.
   this.nodes[fromNode].push(toNode);
   this.nodes[toNode].push(fromNode);
  }
    画像を削除します.
    removeEdge(fromNode, toNode) {//fromNode와 toNode 사이의 간선을 삭제합니다.
    this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode),1);
    this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode),1);
  }
    配列内のスペースを削除(feat.filter()
    仮想マシンLinuxシステムクローン