グラフィック用語

頂点チョウテン:シェイプを作成するノード
幹線:グラフ内のノード間の接続.
頂点序数:頂点(ノード)に接続されている幹線の数を表します.
疎図:頂点間の可能な接続の一部しか存在しない場合、この図を疎図と呼びます.
密図:異なる頂点間に多くの接続がある場合、この図を密図と呼びます.
ループ図:ある頂点からその頂点を返す経路が存在する指向性図を指す.
重み付け:幹線の値を表し、コンテキストによって異なる内容を表すことができます.

// 무지향성 그래프
function UndirectedGraph (){
  this.edges = {};
}

UndirectedGraph.prototype.addVertex = function (vertex) {
  this.edges[vertex] = {};
}

UndirectedGraph.prototype.addEdge = function (vertex1, vertex2, weight) {
  if (weight == undefined) {
    weight = 0;
  }
  this.edges[vertex1][vertex2] = weight;
  this.edges[vertex2][vertex1] = weight;
}

const graph1 = new UndirectedGraph();
graph1.addVertex(1);
graph1.addVertex(2);
graph1.addEdge(1,2,1);
graph1.addVertex(3);
graph1.addVertex(4);
graph1.addVertex(5);
graph1.addEdge(2,3,8);
graph1.addEdge(3,4,10);
graph1.addEdge(4,5, 100);
graph1.addEdge(1,5,88);

//console.log(graph1)

UndirectedGraph.prototype.removeEdge = function (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];
  }
}

UndirectedGraph.prototype.removeVertex = function (vertex) {
  for (let adjacentVertex in this.edges[vertex]) {
    this.removeEdge(adjacentVertex, vertex)
  }
  
  delete this.edges[vertex];
}

const graph2 = new UndirectedGraph();
graph2.addVertex(1);
graph2.addVertex(2);
graph2.addEdge(1,2,1);
graph2.addVertex(3);
graph2.addVertex(4);
graph2.addVertex(5);
graph2.addEdge(2,3, 8);
graph2.addEdge(3,4, 10);
graph2.addEdge(4,5, 100);
graph2.addEdge(1,5, 88);
graph2.removeVertex(5);
graph2.removeVertex(1);
graph2.removeEdge(2,3);

// console.log(graph2)

// 지향성 그래프
function DirectedGraph() {
  this.edges = {};
}

DirectedGraph.prototype.addVertex = function (vertex) {
  this.edges[vertex] = {};
}

DirectedGraph.prototype.addEdge = function (origVertex, destVertex, weight) {
  if (weight === undefined) {
    weight = 0;
  }  
  this.edges[origVertex][destVertex] = weight
}

let digraph1 = new DirectedGraph();
digraph1.addVertex("A");
digraph1.addVertex("B");
digraph1.addVertex("C");
digraph1.addEdge("A", "B", 1);
digraph1.addEdge("B", "C", 2);
digraph1.addEdge("C", "A", 3);

// console.log(digraph1)

DirectedGraph.prototype.removeEdge = function (origVertex, destVertex) {
  if (this.edges[origVertex] && this.edges[origVertex][destVertex] !== undefined) {
    delete this.edges[origVertex][destVertex];
  }
}

DirectedGraph.prototype.removeVertex = function (vertex) {
  for (let adjacentVertex in this.edges[vertex]) {
    this.removeEdge(adjacentVertex, vertex)
  }
  delete this.edges[vertex];
}

グラフループ

1.優先検索幅

図面内で、ノードと対応するノードとの間の幹線を接続するアルゴリズムを順次検索します.
ツリー・データ構造のシーケンス優先順位と同様に、幅優先検索にはキューが必要です.各ノードに接続された各頂点をキューに追加し、キュー内の各エントリにアクセスします.

DirectedGraph.prototype.traverseBFS = function (vertex, fn) {
  let queue = [],
      visited = {};
  
  queue.push(vertex);
  
  while (queue.length) {
    vertex = queue.shift();
    if (!visited[vertex]) {
      visited[vertex] = true;
      fn(vertex);
      for (let adjacentVertex in this.edges[vertex]) {
        queue.push(adjacentVertex);
      }
    }
  }
}

digraph1.traverseBFS("B", (vertex) =>{console.log(vertex)})

時間複雑度:O(V+E)
幅優先探索の場合,時間複雑度はO(V＋E)であった.ここでVの個数は頂点の個数であり、Eは幹線の個数である.グラフィック全体を巡回するために、アルゴリズムはすべての幹線とノードにアクセスする必要があるからです.

2.優先検索深度

深度優先検索とは、グラフィックで他の接続にアクセスする前に、1つの接続を深度検索および巡回する検索アルゴリズムです.

DirectedGraph.prototype.traverseDFS = function (vertex, fn) {
  let visited = {};
  this._traverseDFS(vertex, visited, fn);
}

DirectedGraph.prototype._traverseDFS = function (vertex, visited, fn) {
  visited[vertex] = true;
  fn(vertex);
  for (let adjacentVertex in this.edges[vertex]) {
    if (!visited[adjacentVertex]){
      this._traverseDFS(adjacentVertex, visited, fn);
    }
  }
}

時間複雑度:O(V+E)
深さ優先探索の場合,時間複雑度はO(V＋E)であった.この場合、アルゴリズムは、グラフィック全体を巡回するために、すべての幹線およびノードにアクセスする必要があります.

ウェイト付きグラフィックと最短パス

重み付け幹線の図形

図形の幹線は頂点間の接続を表していることを覚えておいてください.幹線が接続を形成する場合は、その接続に重み値を割り当てることができます.
重みのある幹線図では、最も重要な問題は、どのノードから別のノードへの最短パスが何であるかです.図の最短経路アルゴリズムには多くの種類があり,その中で本論文では多出口アルゴリズムを紹介する.

マルチアウトレットのアルゴリズム:最短パス

マルチ出口アルゴリズムは、各段階で最短経路をとることによって目的地を達成する.最初はノードに到達できない可能性があるため、距離を無限にマークします.次に、各ループループで、各ノードの最短パスを選択します.

function _isEmpty(obj) {
  return Object.keys(obj).length === 0;
}

function _extractMin(Q, dist) {
  let minimumDistance = Infinity,
      nodeWithMinimumDistance = null;
  for (let node in Q) {
    if (dist[node] <= minimumDistance) {
      minimumDistance = dist[node];
      nodeWithMinimumDistance = node;
    }
  }
  return nodeWithMinimumDistance;
}

DirectedGraph.prototype.Dijkstra = function(source) {
  // 정점 집합 Q를 생성한다.
  let Q = {}, dist = {};
  for (let vertex in this.edges){
    dist[vertex] = Infinity;
    Q[vertex] = this.edges[vertex];
  }
  
  dist[source] = 0;
  
  while (!_isEmpty(Q)) {
    let u = _extractMin(Q, dist)
    
    delete Q[u]
    
    for (let neighbor in this._edges[u]) {
      let alt = dist[u] + this.edges[u][neighbor];
      
      if (alt < dist[neighbor]) {
        dist[neighbor] = alt;
      }
    }
  }
  return dist
}

時間複雑度:O(V^2+E)
上記のアルゴリズムは幅優先探索アルゴリズムと類似している.しかし,時間複雑度O(n)のextractmin法が必要である.したがって,上記アルゴリズムの時間的複雑度はO(V^2+E)である.

位相位置合わせ

指向性図では、異なるアプリケーション・ケースで最初に処理すべきノードを理解します.このような例には、タスクスケジューラがあります.タスクスケジューラでは、1つのタスクは、前のタスクが実行されたかどうかに依存します.別の例では、JavaScriptに依存するマネージャで、ライブラリのインポートを実行するときに、そのライブラリの前にインポートする必要があるライブラリを知る必要があります.位相整列アルゴリズムは、これらの機能を実行します.位相ソートアルゴリズムは、スタック記録順序を用いた修正バージョンの深さ優先ソートである.

DirectedGraph.prototype.topologicalSortUtil = function (v, visited, stack) {
  visited.add(v);
  
  for (let item in this.edges[v]){
    if (visited.has(item) === false){
      this.topologicalSortUtil(item, visited, stack)
    }
  }
  stack.unshift(v);
}

DirectedGraph.prototype.topologicalSort = function () {
  let visited = new Set(),
      stack = [];
  
  for(let item in this.edges) {
    if (visited.has(item) === false) {
      this.topologicalSortUtil(item, visited, stack);
    }
  } 
  return stack;
}

時間複雑度:O(V+E)
空間複雑度:O(V)
位相整列アルゴリズムは,単純に付加的なスタックを有する深さ超整列である.従って,位相ソートアルゴリズムの時間的複雑さは深さ優先ソートと同じである.