오답노트

그래프에 대해서 알아보자
https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

공간복잡도에 대해서 알아보자
https://velog.io/@yewon-july/Graph

참조 사이트
https://hibee.tistory.com/294

1.3. 그래프를 구현하는 방법
인접 행렬 (Adjacent Matrix) : 정방 행렬을 사용하는 방법

해당하는 위치의 value 값을 통해서 Vertex 간의 연결 관계를 O(1) 로 파악할 수 있다. Edge 개수와는 무관하게 O(V^2) 의 공간복잡도를 갖는다.

그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우 유리함
두 정점을 연결하는 간선의 존재 여부를 O(1) 안에 즉시 알 수 있다
하지만, 그래프에 존재하는 모든 간선의 수는 O(V^2) 안에 알 수 있다

인접 리스트 (Adjacent List) : 연결 리스트를 사용하는 방법

Vertex 의 인접 리스트를 확인해봐야 하므로 Vertex 간 연결되어있는지를 각각 확인해야한다. 공간복잡도는 O(V+E) 를 갖는다.

그래프 내에 간선의 숫자가 적은 희소 그래프(Sparse Graph) 의 경우 유리함
그래프에 존재하는 모든 간선의 수는 O(V+E) 안에 알 수 있다
하지만, 두 정점 사이에 간선의 존재 여부는 해당 정점의 차수만큼의 시간이 필요하다

이진트리
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