ノートをまちがえる

グラフを見てみましょう.
https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c
空間の複雑さを理解してみましょう.
https://velog.io/@yewon-july/Graph
リファレンスサイト
https://hibee.tistory.com/294
1.3. 図面の実装方法
隣接行列:正方形行列を使用
対応する位置の値により、Vertex間の接続関係をO(1)として決定することができる.Edge個数に関係なくO(V^2)の空間的複雑さを持つ.
図形中の複数の幹線の密集図形(Dese Graph)に有利である
二つの頂点を結ぶ幹線の有無はO(1)内ですぐに分かる
しかし、グラフ上に存在するすべての幹線の数はO(V^2)内で知ることができる.
隣接リストれんけつりすと:接続リストを使用せつぞくりすとをしよう
Vertexの隣接リストを表示する必要があるため、Vertex間に接続があるかどうかを個別に確認する必要があります.空間的複雑度はO(V＋E)である.
グラフ内の線の数が少ない疎グラフ(Sparse Graph)の方が有利です
図中のすべての幹線の数はO(V+E)内で知ることができる.
しかし、2つの頂点の間で、幹線の存在の有無は、その頂点の回数に等しい時間を要する.
バイナリツリー
https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/

Graph

This freak me out
so I watched YOUTUBE.
I am wasted..
https://www.youtube.com/watch?v=cWNEl4HE2OE

グラフは何かを結びつけています.

ここから見ると、いろいろな空港がつながっていて、重要なハブがあるので、それを救うことができます.

ここにもいくつかの空港がつながっていて、一部の空港はつながっていない.

const airports= 'PHX BKK OKC JFK LAX MEX EZE HEL LOS LAP LIM'.split(' ');

const routes = [
    ['PHX', 'LAX'],
    ['PHX', 'JFK'],
    ['JFK', "OKC"],
    ['JFK', 'HEL'],
    ['JFK', 'LOS'],
    ['MEX', 'LAX'],
    ['MEX', 'BKK'],
    ['MEX', 'LIM'],
    ['MEX', 'EZE'],
    ['LIM', 'BKK'],
];


// The graph
const adjacencyList = new Map();

// Add node
function addNode(airport) {
  adjacencyList.set(airport, []);
}

// Add edge, undirected
function addEdge(origin, destination) {
  adjacencyList.get(origin).push(destination);
  adjacencyList.get(destination).push(origin);
}

//Create the graph

airports.forEach(addNode);
routes.forEach(route => addEdge(...route))

-> 여기 rest parameter 씀

console.log(adjacencyList)

この結果.

この取引は不思議ですね.

Map(11) {"PHX" => Array(2), "BKK" => Array(2), "OKC" => Array(1), "JFK" => Array(4), "LAX" => Array(2), …}
[[Entries]]
0: {"PHX" => Array(2)}
key: "PHX"
value: (2) ["LAX", "JFK"]
1: {"BKK" => Array(2)}
key: "BKK"
value: (2) ["MEX", "LIM"]
2: {"OKC" => Array(1)}
key: "OKC"
value: ["JFK"]
3: {"JFK" => Array(4)}
key: "JFK"
value: (4) ["PHX", "OKC", "HEL", "LOS"]
4: {"LAX" => Array(2)}
key: "LAX"
value: (2) ["PHX", "MEX"]
5: {"MEX" => Array(4)}
key: "MEX"
value: (4) ["LAX", "BKK", "LIM", "EZE"]
6: {"EZE" => Array(1)}
key: "EZE"
value: ["MEX"]
7: {"HEL" => Array(1)}
key: "HEL"
value: ["JFK"]
8: {"LOS" => Array(1)}
key: "LOS"
value: ["JFK"]
9: {"LAP" => Array(0)}
key: "LAP"
value: []
10: {"LIM" => Array(2)}
key: "LIM"
value: (2) ["MEX", "BKK"]
size: (...)

金珠慧が教えてくれた...うん.ちょっと難しいことを知っているようですが...

Graph Search or Traversary

watsted 2

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

  addNode(node) {
    this.nodes[node] = this.nodes[node] || [];
  }

  contains(node) {
    if (this.nodes[node]) {
      return true;
    } else {
      return false;
    }
  }

  removeNode(node) {
    if (!this.nodes[node]) {
      return undefined;
    } else {
      for (let element of this.nodes[node]) {
        this.removeEdge(node, element); /// hoisting
      }
    }
    delete this.nodes[node];
    return this.nodes;
  }
  /**
   * 노드를 제거한다. (delete)
   * 노드를 제거할 경우 edge도 함께 제거되어야함
   * 빈 그래프일 경우 아무것도 안해야됨
   * 노드와 연결된 edge가 있는지 확인 (!this.nodes[node] 조건이 충족하지 않다면 edge가 있다고 판단)
   * removeEdge()를 사용하기 위해 인자로 전달될 요소를 정해야됨
   * 반복문을 이용해 node와 연결된 node에 접근
   * 접근된 node의 edge 제거
   */

  hasEdge(fromNode, toNode) {
    if (this.nodes[fromNode]) {
      for (let element of this.nodes[fromNode]) {
        if (element === toNode) {
          return true;
        }
      }
    }
    return false;
  }
  /**
   * fromNode가 있을 경우 (없으면 입력받은 요소를 확인할 수 없으니 false)
   * fromNode의 배열을 모두 돌면서
   * 입력받은 요소와 들어있는 요소가 같으면 true
   * 아니면 false
   */

  addEdge(fromNode, toNode) {
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

  removeEdge(fromNode, toNode) {
    this.nodes[fromNode].pop(toNode);
    this.nodes[toNode].pop(fromNode);
  }
}

let graph = new Graph(3);

graph.addNode(1);
graph.addNode(2);

graph.addEdge(1,2)

module.exports = Graph;
console.log(graph);

今日はやります.

カンヌ学院のグラフを説明します。https://ko.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/describing-graphs

Graph Data Structure in JavaScript: https://medium.com/@ziyoshams/graphs-in-javascript-cc0ed170b156