[algorithm] 그래프 기초

<graph의 종류>

graph는 크게 아래 두가지로 나뉜다

 - directed graph (방향 그래프)

 - undirected graph (무방향 그래프)

그 기준은 edge에 따라 갈리는데, edge는 graph의 구성요소 중 하나이다. graph의 구성요소는 아래와 같다

 - vertex(정점)

 - edge(간선)

    - directed or not

    - weighted or not

edge가 directed edge이면 directed graph가 되는것이다.

<graph의 구현>

그리고 그래프의 구현(implementation)은 아래 두가지로 나뉜다

 - adjust matrix (인접행렬)

    - index를 통한 빠른 vertex 접근

    - sparse graph일수록 공간 효율이 떨어짐 (<-> dense graph일수록 높아짐)

    - adjust vertices를 순회할 때 O(V)

 - adjust list (인접리스트)

    - adjMatrix와 반대의 특징을 가짐

    - adjust vertices를 순회할 때 O(E) (모든 edge가 해당 vertex의 adj edge일 때)

 - (incidence matrix/list도 있는듯..?)

위에서 saprse/dense graph가 나왔는데, edge가 적음/많음에 따라 graph를 아래와 같이 나눌수도 있다

 - sparse graph (희귀 그래프)

 - dense graph (밀집 그래프)