[Data Structure] Graph

그래프(Graph)는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 구성되어 있다. 또한 간선에 의해 연결된 2개의 노드가 대칭인 무방향(undirected)일 수도, 2개의 노드가 비대칭인 유방향(directed)일 수도 있다. 도로로 연결된 도시의 지도, 소셜 미디어에서 상호 연결된 사용자 등이 실생활에서 그래프라는 자료구조가 활용되고 있는 사례이다.
이미지 출처: codestates urclass

용어 정리

• 노드(Node): 정점(vertice)이라고도 하며 노드에는 데이터가 저장됨
• 간선(Edge): 노드 간의 관계를 나타냄
• 진입 차수(in-degree): (유방향 그래프에서) 외부 노드에서 들어오는 간선의 수
• 진출 차수(out-degree): (유방향 그래프에서) 한 노드에서 외부로 향하는 간선의 수

그래프 구현 방식

1. 인접 행렬(Adjacency Matrix) 방식
인접 행렬 방식은 NxN 행렬에서 2차원 배열을 생성하여 graph[i][j]에 1과 0으로 true와 false 값을 저장하는 방식으로, 값이 true일 경우 간선이 있음을 의미한다. 노드 간 간선 여부를 한 번의 접근으로 확인할 수 있는 O(1)의 시간복잡도를 갖는다. 그래프에 간선이 많이 존재하는 곳(밀집 그래프)에 유용하다. 단, 낭비되는 공간이 많다는 단점이 있다.

2. 인접 리스트(Adjacency List) 방식
인접 리스트 방식은 각 노드마다 연결리스트를 갖게하는 방식이다. 노드 간 간선 여부를 알기 위해서는 리스트를 처음부터 순회해야 하는 O(n)의 시간복잡도를 갖는다. 그래프에 간선이 적게 존재하는 곳(희소그래프)에 유용하다. 공간을 효율적으로 사용할 수 있다.

JS 코드 구현(무방향 그래프)

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

  addNode(node) {
    this.nodes[node] = this.nodes[node] || [];
  }
//그래프에 해당 노드가 존재하는지 여부
  contains(node) {
    if(this.nodes[node]){
      return true;
    }else{
      return false;
    }
  }
//그래프에서 노드를 삭제
  removeNode(node) {
    for(let key in this.nodes){
      this.removeEdge(key, node);
    }
    delete this.nodes[node];
  }
//fromNode와 toNode 사이의 간선 존재 여부를 반환
  hasEdge(fromNode, toNode) {
    let newNode = this.nodes[fromNode];
    if(newNode){
      for(let el of newNode){
        if(el === toNode){
          return true;
        } 
      }
    }
    return false;
  }

//fromNode와 toNode 사이의 간선을 추가
  addEdge(fromNode, toNode) {
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

//fromNode와 toNode 사이의 간선을 삭제
  removeEdge(fromNode, toNode) {
    this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1);
    this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1);
 }
}