Graph

그래프는 노드(혹은 vertex)와 그 노드를 연결하는 간선(edge)로 이루어진 자료구조로서 무방향(undirected)일 수 있다. 즉 간선(edge)에 의해 연결된 2개의 노드가 대칭 일 수 있다는 말이다, 그렇다면 방향성을 가질 수 도 있다는 의미 인데. 이는 노드가 비대칭 관계라는 의미이다.

undirected graph & directed graph

• 무방향 그래프(undirected graph)

위 그림처럼 간선(edge)에 방향성이 없고 모든 간성들은 양방향 이동이 가능한 그래프이다.

• 방향 그래프(directed graph)

위 그림처러 간선(edge)이 순서가 있는 그래프로 방향성을 가지고 있다.
방향은 한가지 방향만 가질 수 있는 것이 아닌 양방향을 가질수도 있다.

그래프를 표현하는 방법

1. 인접 행렬(adjaceney matrix)

N개의 정점을 가진 그래프의 인접 행렬은 위의 그림처럼 2차원 리스트에 저장할 수 있다.
정점과 정점이 서로 연결되어 있다면 1을 서로 연결되어 있지 않다면 0을 저장하는 방법으로 undirected graph의 경우에는 가운데의 대각선을 기준으로 서로 대칭을 이루게 된다.

2. 인접 리스트(adjacency list)

N개의 정점을 가진 그래프의 인접 리스트는 위의 그림처럼 Linked List처럼 node에 담아 연결을 할 수 있다.

그래프 구현

• 그래프 메서드

  • addNode(node) - 주어진 node를 그래프에 추가하는 메서드로 node의 값이 falsy한 값이라면 빈배열로 저장한다.
  • contains(node) - 현재 그래프에 해당 node가 있는지 여부를 반환한다.
  • removeNode(node) - 주어진 node를 그래프에서 제거하는 메서드
  • hasEdge(fromNode, toNode) - 주어진 fromNode와 toNode사이에 간선(edge)의 존재 여부를 반환한다.
  • addEdge(fromNOde, toNode) - 주어진 fromNode와 toNode사이에 간선(edge)를 추가한다.
  • removeEdge(fromNode, toNode) - 주어진 fromNode와 toNode사이에 간선(edge)를 제거한다.

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.hasOwnProperty(node);
  }

  removeNode(node) {
    if (this.nodes[node].length === 0) {
      delete this.nodes[node];
    } else {
      for (const value of this.nodes[node]) {
        this.removeEdge(node, value);
      }
    }
  }

  hasEdge(fromNode, toNode) {
    let bool = false;
    const from = this.nodes[fromNode].some((el) => el === toNode);
    if (from) {
      bool = true;
    }
    return bool;
  }

  addEdge(fromNode, toNode) {
    this.nodes[fromNode].push(toNode);
    this.nodes[toNode].push(fromNode);
  }

  removeEdge(fromNode, toNode) {
    this.nodes[fromNode].splice(this.nodes[fromNode].indexOf(toNode), 1);
    this.nodes[toNode].splice(this.nodes[toNode].indexOf(fromNode), 1);
  }
}