그래프 표현

1. [자료구조]  그래프의 표현 

  ㅇ [기초 표현]  그림으로 나타냄
  ㅇ [기호 표현]  정점들의 관계를 나타내는 연결선들의 집합으로 표현 : G = (V,E)
  ㅇ [자료구조 표현]
     - (행렬)  인접 행렬 (Adjacency Matrix) 및 부속/근접 행렬 (Incidence Matrix)
        . 모든 관계를 전부 저장하는 방식 (특정 노드 간 연결성 확인 용이)
     - (리스트)  인접 리스트 (Adjaency List)
        . 연결된 정보 만을 저장하는 방식 (메모리 효율적)


2. [자료구조]  인접 행렬 (Adjaency Matrix)

  ㅇ 그래프를 행렬로 표현하는 방식 중 하나

  ㅇ 그래프의 행렬 표현 방식의 특징
     - 행렬 크기가, n x n 임 (n : 정점의 수)
        . 즉, 공간 복잡도가, O(n2) 임 
     - 각 행,열이 정점을 나타냄
        . 각각의 행을 정점으로 보고, 열을 자신을 포함한 다른 정점으로 봄
        . 즉, 인접 노드들 모두를 확인하기 위한, 시간 복잡도가, O(n) 임 
     - 각 행,열이 만나는 원소가 간선을 나타냄
        . 두 정점 간 교차점에, 연결선의 수 또는 가중치를 부여 가능
     - 특정 두 정점 간의 연결성 확인이 쉬움
        . 간선 존재 여부를 원소의 값의 유무(0 이면 연결선 존재 안함)로 쉽게 파악 가능
        . 즉, 연결성 확인에 대한, 시간 복잡도가, O(1) 임
     - 이해하기 쉬움

  ㅇ `방향 그래프`의 경우에, 인접 행렬 표현의 例
     - 행렬 원소 값 : 정점들 간에 화살의 개수
        . (만일, 1 이면 연결선 존재, 0 이면 연결선 존재 안함)
     
        . v1,v3 각각 자신으로의 화살 1개
        . v1에서 v2로의 화살 0개
        . v2에서 v1로의 화살 1개 
        . v2에서 v3로의 화살 2개
        . v3에서 v1로의 화살 1개 

     - 특징
        . (비 대칭성)  행렬이, 비 대칭적인 형태를 갖음
        . (연결 관계)  타 정점을 가리키는 정점인 경우에 만 값이 부여됨
        . (총합 = 연결선의 수)  결국, 행렬 원소의 총합이 연결선의 수와 같아짐

  ㅇ `무 방향 그래프`의 경우에, 인접 행렬 표현의 例
     - 행렬 원소 값 : 정점들 간에 결합되는 연결선의 개수
     
        . v1,v3가 자기 자신과 결합되는 간선 수 2개
        . v2와 v3 간에 결합 연결선 수 2개
        . v1와 v3 간에 결합 연결선 수 1개

     - 특징
        . (대칭성)  행렬이, 대칭 행렬의 형태를 갖음
        . (차수 결정 용이)  행 또는 열을 합해 얻은 수와 같음
           .. (차수 : 정점에 연결된 연결선의 수)

  ㅇ '가중 무방향 그래프`의 경우에, 인접 행렬 표현의 例)
      


3. [자료구조]  부속 행렬, 근접 행렬 (Incidence Matrix)

  ㅇ 그래프를 행렬로 표현하는 또다른 방식
     - 각 행이, 정점(또는,연결선)을, 
     - 각 열이, 연결선(또는,정점)을 나타내게 함


4. [자료구조]  인접 리스트 (Adjaency List)

  ㅇ 그래프 내 각 정점 마다, 인접 연결선들을 단순 연결 리스트(Linked List)로 표현한 것
     - 각 정점 마다 하나씩, 총 |V|개의 정점 수 만큼의 연결 리스트들로 구성됨

      

     - 만일,
        . 무향 그래프이면, 각 간선이 2번씩 연결 리스트에 나타남
        . 방향 그래프이면, 각 간선이 1번 만 연결 리스트에 나타남

  ㅇ 구현 방법
     - 우선, 모든 정점들을 배열로써 표현
        . 정점 번호들을 배열의 인덱스로 사용
     - 그리고, 각 정점(배열 원소)에다가 인접한 정점들을 연결 리스트로 표현
        . 각 정점의 배열 내 요소는 인접한 모든 정점의 목록이 됨

  ㅇ 특징
     - (효율적 기억장소 활용)
        . 각 연결선 마다 연결 리스트 항목에 하나씩 대응되므로,
        . 존재 않는 연결선을 표현 안하므로, 기억장소 낭비가 적음
     - (각 정점의 이웃 순환이 용이)
        . 각 정점별 연결 리스트를 따라가기 만 하면 됨
        . 즉, 인접 노드들 모두를 확인하기 위한, 시간 복잡도가, O(d(v)) 임 
           .. (여기서, d(v)는 그래프 차수 임)
     - (특정 두 정점 간의 연결성 확인에 불편)
        . 시간 복잡도가, O(n) 임
        . 즉, 최악의 경우 모든 정점들을 다 확인해야 됨


4. [자료구조]  그래프를 자료구조로써 표현(구현)할 때의 유의점

  ㅇ 트리, 그래프의 표현 상 비교
     - 트리는, 주로 노드 위주로, 구조 정보의 표현을 함
     - 그래프는, 주로 연결선 위주로, 구조 정보의 표현을 함
        . 이때, 주로, 인접 리스트를 많이 사용 (array of adjacency lists)
           .. 즉, 프로그래밍 언어 내 연결 리스트를 구현한 내장 배열 구조를 많이 사용하는 편 임
        . 다만, 각 노드는, `명칭(라벨)`,`방문 여부` 정도는 유지할 필요 있음

  ㅇ 만일, 그래프를, 클래스 형식으로 표현한다면, 다음 사항들이 항상 추적 가능해야 함
     - 총 노드 갯수는 얼마인가?
     - 각 노드 마다 연결선 갯수는 얼마인가? 등