Graph

Graph란?

->노드(Node 또는 정점(vertex)라고도 부른다), 그리고 노드와 노드를 연결하는 간선(edge)로 구성 돼 있다.
-> 방향성을 갖을 수도 있고(Directed), 방향성이 없을 수도 있다(Undirected).
-> 하나 이상의 사이클을 갖고 있으면 Cyclic Graph이라고 하고, 사이클이 하나도 없으면 Acyclic Graph 라고 한다.

Graph를 표현하는 방법

1. Adjacency Matrix
   -> 2차원 배열에 표현.
   -> 그래프를 표에 표현하는 방법으로 서로 연결된 노드는 1(직접적으로 연결),
   연결이 없으면 0으로 채워준다.
   
2. Adjacency List
   -> 배열의 노드들을 나열하고 관계를 Linked List로 표현.
   -> 배열방에 모든 노드를 집어넣고 각 배열방에 있는 해당 노드와
   인접한 노드를 Linked list로 나열해준다.
   

Graph 구현하기

//클래스 생성

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

//노드 추가

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

//그래프에 노드가 있는지 확인

  contains(node) {
    return this.nodes[node] ? true : false;
  }

//그래프에서 노드 삭제

  removeNode(node) {
    for (let a of this.nodes[node]) {
      let nodeIndex = this.nodes[a].indexOf(node);
      this.nodes[a].splice(nodeIndex, 1);
      let nodeIndex1 = this.nodes[node].indexOf(a);
      this.nodes[node].splice(nodeIndex1, 1);
    }
    delete this.nodes[node];
  }
  
  //간선이 있는지 확인
  
  hasEdge(fromNode, toNode) {
    if (this.nodes[fromNode].includes(toNode)) {
      return true;
    }
    return false;
  }
  
//간선(Edge) 추가

  addEdge(fromNode, toNode) {
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }
  
//간선(Edge) 삭제

  removeEdge(fromNode, toNode) {
    if (this.hasEdge(fromNode, toNode)) {
      let nodeIndex = this.nodes[fromNode].indexOf(toNode);
      this.nodes[fromNode].splice(nodeIndex, 1);
      nodeIndex = this.nodes[toNode].indexOf(fromNode);
      this.nodes[toNode].splice(nodeIndex, 1);
    }
  }
}