Data Structure 공부 중 이해한 부분을 정리합니다. 각 자료구조의 구현은 JavaScript를 이용하였습니다.

Graph

노드(Node, 또는 정점-vertax-), 노드와 노드를 연결하는 간선(edge)로 구성됩니다.

Graph의 종류

그래프의 종류로는 무방향 그래프와 방향 그래프가 있습니다.

• 무방향 그래프
  무방향 그래프는 방향이 없는 그래프로 간선을 통해 양 뱡향 모두 갈 수 있습니다.

• 방향 그래프
  방향 그래프는 방향이 존재하는 그래프로 지정된 방향으로만 이동 할 수 있습니다.
  (방향 그래프에서 진입 차수(in-dgree)는 외부에서 오는 간선의 수이며, 진출 차수(out-dgree)는 외부로 향하는 간선의 수 입니다.)

Graph의 구현 방식

인접행렬 방식

• 인접 행렬은 n * n 불린(Boolean)행렬이며,
  graph[i][j]가 true이면 i->j로의 간선이 있다는 뜻 입니다.
• 무방향 그래프를 인접행렬로 표형하면 대칭이 됩니다.
• 그러나 간선 수와 무관하게 V^2의 메모리 공간이 필요합니다.

인접리스트 방식

• 가장 일반적인 방법으로 각각의 노드에 인접한 노드를 리스트에 저장합니다.
• 무방향 그래프는 연결된 노드 각자에 노드를 저장하기 때문에 V+2E 메모리 공간이, 방향 그래프는 방향당 한 번 저장하기 때문에 V+E 메모리 공간이 필요합니다.

Graph 구현 💻

구현한 메소드

• addNode(node) - 그래프에 노드를 추가합니다.

• addEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 추가합니다.

• removeNode(node) - 그래프에서 노드를 삭제합니다.

• removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.

• hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.

• contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.

Pesuedo Code

• addNode(node) - 매개변수인 node의 인자로 들어오는 값을 key로 하고 value를 간선으로 이어진 노드를 추가할 빈 배열을 전체 그래프에 추가합니다.

• addEdge(fromNode, toNode) - fromNode와 toNode의 value값인 배열에 각 toNode와 fromNode를 추가합니다.

• removeNode(node) - graph의 key

• removeEdge(fromNode, toNode) - graph의 fromNode와 toNode의 키의 value에서 각각toNode,fromNode값이 있는 인덱스를 찾아 splice를 이용해 제거합니다.

• hasEdge(fromNode, toNode) - fromNode와 toNode의 value값에 각각 서로의 노드가 있으면 true를 return하고 아니면 false를 return 합니다.

• contains(node) - graph의 key에 node가 있으면 true를 return하고 아니면 false를 return 합니다.

구현은 무방향 그래프, 인접 리스트 방식으로 구현하였습니다.

class Graph {
  constructor() {
    this.nodes = {};
  }

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

  contains(node) {
    return this.nodes.hasOwnProperty(node);
  }

  removeNode(node) {
    for(let i of this.nodes[node]){
      let index = this.nodes[i].indexOf(node);
      this.nodes[i].splice(index,1);
    }

    delete this.nodes[node];
  }

  hasEdge(fromNode, toNode) {
    if(this.nodes[fromNode].includes(toNode)){
      if(this.nodes[toNode].includes(fromNode)){
        return true;
      }
    }
    return false;
  }

  addEdge(fromNode, toNode) {
    if(!this.contains(fromNode) || !this.contains(toNode)){
      return ;
    }
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

  removeEdge(fromNode, toNode) {
    if(!this.contains(fromNode) || !this.contains(toNode)){
      return ;
    }

    let toNodeindex = this.nodes[fromNode].indexOf(toNode);
    let fromNodeindex = this.nodes[toNode].indexOf(fromNode);
    this.nodes[fromNode].splice(toNodeindex,1);
    this.nodes[toNode].splice(fromNodeindex,1);
  
  }
}