[Algorithm]그래프(Graph)의 정의 - 그래프의 표현

1. 표현 방법

   a. 인접 행렬(adjacency martix)

     - 그래프 G = (V, E)가 n>=1개의 정점을 가짐, G의 인접 행렬은 크기가 n x n인 2차원 배열로 정의

     -  인접행렬로 표현하는데 필요한 공간= n^비트

     -  무방향 그래프일 때: 간선(i, j) ∈ E(G) -> 간선(j,i) ∈ E(G)

          -> 행 i의 합 = 정점 i의 차수

      - 방향 그래프일 때: 행 i의 합 = 정점 i의 진출 차수,  열 i의 합 = 정점 i의 진입 차수

  b. 연결리스트(Adjacency list): n개의 정점에 대한 인접한 정점 리스트로 만듦

      =  연결 리스트로 구현한 인접리스트: 

         - 각각의 정점 리스트는 헤더 노드와 리스트 노드로 구성

         - 리스트 노드는 vertex 필드, link 필드로 구성함

         - n개의 정점, e개의 간선일 때 -> 무방향 그래프: n개의 헤더노드, 2e개 리스트 노드 필요

                                                         -> 방향 그래프: n개의 헤더 노드, e개의 리스트 노드 필요

  c. 인접리스트: 배열을 이용하여 순차 표현으로 구현한 인접 리스트

     - 리스트 노드를 순차적으로 묶어 배열로 저장

     - n개의 정점, e개의 간선을 가진 그래프 vertex[n+2e+1]로 표현

     - vertex[i] : 정점 i (0 ≤i≤ n)에 인접한 너드들이 저장되기 시작하는 위치의 인덱스
     - vertex[n] : 배열의 크기인 n+2e+1를 저장

         i) 배열: 리스트 시작과 배열 크기정보에 정점마다 가르키는 번호 작성

         ii) 정점의 차수: 정점에 부속된 간선의 수(노드의 개수) = O(n + e)

         iii) 방향그래프에서 정점의 차수: 진출 차수(단순 인접노드의 개수만 계산)

         v) 역인접 리스트: 모든 정점 각각에 대한 노드를 포함

  d. 인접 다중 리스트

     i) 다중 리스트: 노드들이 여러 리스트들이 공용하는 리스트

     ii) 각 간선 하나에 노드가 만들어지고, 이 노드는 간선이 부속된 두 정점 각각에 대한 인접리스트에 의해 공용

     iii) 노드 구조

     v) G1에 대한 인접 다중리스트 식별 방법: 정점 0의 경우