그래프(Graph)

그래프는 노드(Node, 또는 정점 -vertex- 이라고도 부릅니다), 그리고 노드와 노드를 연결하는 간선(edge)으로 구성됩니다. 그래프는 무방향(undirected)일 수 있습니다. 이는 간선에 의해 연결된 2개의 노드가 대칭일 수 있다는 의미입니다. 한편 방향성(directed)을 가질 수도 있는데, 이는 비대칭 관계를 의미합니다. 이번 스프린트에서는 무방향 그래프를 구현합니다.

그래프(Graph) 용어

• 노드(node) : 정점(vertice)라고도 불리며, 일반적으로 노드에는 데이터가 저장됨

• 간선(edge): 링크, arcs라고도 불리며, 노드간의 관계를 나타냄

• 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점. 위 그림에서 노드A와 B는 인접 정점이라고 할 수 있다

• 단순 경로(simple-path): 경로 중 반복되는 정점이 없는것, 같은 간선을 자나가지 않는 경로

• 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수. 위 그래프에서 A의 차수는 3이다.

• 진출차수(out-degree)/진입차수(in-degree) : 방향그래프에서 사용되는 용어

  진출 차수 는 한 노드에서 외부로 향하는 간선의 수,

  진입차수 는 외부 노드에서 들어오는 간선의 수

그래프(Graph) 종류

• 그래프는 node(혹은 vertice)와 edge(혹은 arcs)로 구성되어 있으며 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조로 네트워크 모델이다.
• 방향성에 따라 undirected graph 와 directed graph 로 나뉘며 간선에 비용이나 가중치를 할당하는 가중치 그래프(weighted graph)가 있다.
• 무방향 그래프(undirected graph): 간선을 통해 양방향으로 이동하며, 정점A와 정점B를 연결하는 간선은 (A, B)와 같이 쌍으로 표현한다.
• 방향 그래프(directed graph): 간선에 방향성이 존재한다. A →B 로만 갈 수 있는 간선은 <A, B>로 표시한다. <A, B> 와 <B, A>는 다르다.
• 가중치 그래프(weighted graph): 간선에 비용이나 가중치가 할당된 그래프로 ‘네트워크(Network)’라고도 한다.

그래프(Graph)그래프(Graph) 의 구현 방식

그래프의 표현 방식은 인접 행렬과 인접 리스트 두가지 방식으로 나눌 수 있다.

인접 리스트(Adjacency List)

• 노드에 연결되어 있는 노드 들을 리스트 로 표현한것이다. 방향・가중치 그래프가 주어졌을 때 연결되어 있는 상황을 인접리스트로 출력할 수 있다.
• 연결된 간선의 정보만을 저장하여 O(E)의 공간을 요구하여 공간 효율성이 우수하지만 두 정점이 서로 연결되어 있는 지 확인하기 위해 O(v)의 시간을 요구한다.

인접 행렬(Adjacency matrix)

• 인접행렬은 노드를 2차원 배열로 만든 것이다. 무방향 그래프에 가중치가 없는 그래프일 경우 인접행렬로 표현할 수 있다.
• 모든 정점들의 연결여부를 저장하여 O(V2)의 공간을 요구 하므로 공간 효율성이 떨어지지만 두 정점이 서로 연결되어 있는 지 확인하기 위해 O(1)의 시간을 요구한다.

그래프(Graph) method

• .addNode() : 새로운 node를 생성하여 그래프에 추가한다.
• .contains() : node.value가 존재하는 지 확인하고 boolean 값을 출력한다.
• .removeNode() : node를 삭제하고, 연결되어 있는 간선 또한 제거한다.
• .addEdge() : 새로운 edge 를 생성하여 두 개의 노드를 연결한다.
• .hasEdge() : node가 서로 연결되어 있는 지 확인하여 boolean 값을 출력한다.
• .removeEdge() : node를 연결하는 edge를 제거한다.
• .forEachNode() : 각 노드를한 번씩 호출하여 그래프를 통과한다.

그래프(Graph) method 구현하기

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

  addNode(node) {
    //addNode(node) - 그래프에 노드를 추가합니다.
    this.nodes[node] = this.nodes[node] || [];
  }

  contains(node) {
    //contains(node) - 그래프에 해당 노드가 존재하는지 여부를 반환합니다.
    if(this.nodes[node]) {
      return true;
    }
    return false;
  }

  removeNode(node) {
    //removeNode(node) - 그래프에서 노드를 삭제합니다.
    if(!this.nodes[node]) {
      return undefined;
    } else {
      if(this.nodes[node].length !== 0) {
        for(let edge of this.nodes[node]) {
          this.removeEdge(node, edge);
        }
      }
      delete this.nodes[node];
      return this.nodes;
    }
  }

  hasEdge(fromNode, toNode) {
    //hasEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선 존재 여부를 반환합니다.
    for(let i of this.nodes[fromNode]) {
      if(i === toNode) {
        return true;
      }
    }
    return false;
  }

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

  removeEdge(fromNode, toNode) {
    //removeEdge(fromNode, toNode) - fromNode와 toNode 사이의 간선을 삭제합니다.
    delete this.nodes[fromNode].pop(toNode);
    delete this.nodes[toNode].pop(fromNode);
  }
}

module.exports = Graph;