Graph

1)정의

:어떤 자료나 개념을 표현하는 정점들의 집합V와 이들을 연결하는 간선들의 집합E로 구성된 자료구조

2)예시

SNS에서 사람들과의 관계,네비게이션(길찾기)과 같이 수많은 정점을 가지고 서로 관계가 있는 정점은 간선으로 이어져 있다.

3)알아둬야할 용어

-정점(vertex): 위치라는 개념. (node 라고도 부름)
-간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름)
-인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점
-정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수
무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배
-진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름)
-진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 간선의 수 (외차수 라고도 부름)
-방향 그래프에 있는 정점의 진입 차수 또는 진출 차수의 합 = 방향 그래프의 간선의 수(내차수 + 외차수)
-경로 길이(path length): 경로를 구성하는 데 사용된 간선의 수
-단순 경로(simple path): 경로 중에서 반복되는 정점이 없는 경우
-사이클(cycle): 단순 경로의 시작 정점과 종료 정점이 동일한 경우

4)특징

-그래프는 네트워크 모델 이다.
-2개 이상의 경로가 가능하다.
-즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
-self-loop 뿐 아니라 loop/circuit 모두 가능하다.
-루트 노드라는 개념이 없다.
-부모-자식 관계라는 개념이 없다.
-순회는 DFS나 BFS로 이루어진다.
-그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
-그래프는 크게 방향 그래프와 무방향 그래프가 있다.
-간선의 유무는 그래프에 따라 다르다.

5)종류

(1)방향그래프 : 각 간선이 방향이라는 새로운 속성을 가지고 있는 그래프
(2)무향그래프: 간선에 방향이 없는 그래프
(3)가중치그래프:각 간선에 가중치라고 불리는 실수 속성을 부여하는 그래프
(4)다중그래프:두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프
(5)단순그래프: 두 정점 사이에 최대 한 개의 간선만 있는 그래프
(6)이분그래프: 그래프 정점들을 겹치지 않는 두개의 그래프

6)구현

(1)인접 행렬
:인접 행렬은 NxN 불린 행렬(Boolean Matrix)로써 matrix[i][j]가 true라면 i -> j로의 간선이 있다는 뜻이다.

class UndirectedGraph {
  constructor() {
    this.edges = {};
  }
  // 정점 추가하기
  addVertex(vertex) {
    this.edges[vertex] = {}; // 객체에서 []를 쓰면 그게 키(key)라는 얘기
  }

  // 간선 추가하기
  addEdge(vertex1, vertex2, weight) {
    if (weight === undefined) {
      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 adjacentVertex in this.edges[vertex]) {
      this.removeEdge(adjacentVertex, vertex);
    }
    delete this.edges[vertex];
  }
}

(2)인접 리스트
:모든 정점(혹은 노드)을 인접 리스트에 저장한다. 즉, 각각의 정점에 인접한 정점들을 리스트로 표시한 것