Graph

그래프는 객체 간의 연결을 시각적으로 표현한 것이다. 그래프는 상하 구조가 없고, 노드(정점, vertex)와 노드를 연결하는 선으로 만들어진 데이터 형식이다. 즉 그래프 자료구조는 루트 노드의 개념, 부모-자식의 관계의 개념이 없다. 서로 평등한 네트워크 모델의 자료구조다.

사례	항목	연결
웹사이트	웹페이지	링크
지도	교차로	도로
소셜미디어	사람	친구 맺기
전화	전화번호	전화선

용어

• 정점(vertex): 그래프를 형성하는 노드
• 간선(엣지, edge): 노드 간의 연결선
• 정점차수(degree of vertex): 노드에 연결된 엣지의 개수
• 방향 그래프(direct): 간선에 방향성이 존재한다.(A -> B), (B -> A)는 서로 다르다.
• 무방향 그래프(undirect): 간선에 방향성이 존재하지 않는다. 서로 연결된 한 쌍으로써만 존재.
• 가중치:(weight): 엣지에 대한 값으로 문맥에 따라 다양한 것을 나타낼 수 있다.
• 희소 그래프(sparse graph): 정점들 간에 가능한 연결 중 일부만 존재하는 경우 희소 구래프라고 한다.
• 밀집그래프:(dense graph): 다양한 정저들 간에 연결이 많은 경우를 밀집 그래프라고 한다.
• 순환 그래프(cyclical graph): 어떠 정점에서 출발해 해당 정점으로 다시 돌아오는 경로가 존재하는 지향성 그래프를 의미한다.

사용예시

• 지하철노선
• graphql
• neo4j

구현

Undirected(방향성X)

class UndirectedGraph {
  constructor() {
    this.edges = {};
  }

  // 노드 생성
  addVertex(vertex) {
    this.edges[vertex] = {};
  }

  // 간선 연결
  addEdges(vertex1, vertex2, weight = 0) {
    this.edges[vertex1][vertex2] = weight;
    this.edges[vertex2][vertex1] = weight;
  }

  // 간선 제거
  removeEdge(vertex1, vertex2) {
    if (this.edges[vertex1] && this.edges[vertex1][vertex2] !== undefined) {
      delete this.edges[vertex1][vertex2];
    }
    if (this.edges[vertex2] && this.edges[vertex2][vertex1] !== undefined) {
      delete this.edges[vertex2][vertex1];
    }
  }

  // 노드 제거
  // 노드가 제거되면, 연결되어있던 모든 간선도 같이 제거되어야 한다.
  removeVertex(vertex) {
    for (let currentVertex in this.edges[vertex]) {
      this.removeEdge(currentVertex, vertex);
    }
    delete this.edges[vertex];
  }
}

const ugraph = new  UndirectedGraph();

ugraph.addVertex(1);
ugraph.addVertex(2);
ugraph.addVertex(3);
ugraph.addEdges(1,2,3);
ugraph.addEdges(1,3,5);

ugraph.removeVertex(1);
console.log(ugraph);

Directed(방향성O)

class DirectedGraph {
  constructor() {
    this.edges = {};
  }

  // 노드 추가
  addVertex(vertex) {
    this.edges[vertex] = {};
  }

  // 노드 연결
  // 방향성이 있어야 하기 때문에 출발점/도칙점이 있다.
  addEdges(start, end, weight = 0) {
    this.edges[start][end] = weight;
  }

  // edge 객체에서 원점이 되는 정점만 삭제하면 된다.
  removeEdge(start, end) {
    if (this.edges[start] && this.edges[start][end] !== undefined) {
      delete this.edges[start][end];
    }
  }

  removeVertex(vertex) {
    for (let currentVertex in this.edges[vertex]) {
      this.removeEdge(currentVertex, vertex);
    }
    delete this.edges[vertex];
  }
}

const dgraph = new DirectedGraph();

dgraph.addVertex(1);
dgraph.addVertex(2);
dgraph.addVertex(5);

dgraph.addEdges(1, 5, 5);
dgraph.addEdges(1, 2);
console.log(dgraph);

참고자료

• 그래프 자료구조