그래프 표현

(2021-03-04)

Adjaency Matrix, 인접 행렬, Adjaency List, 인접 리스트

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

  ㅇ [기초 표현]  그림으로 나타냄
  ㅇ [기호 표현]  정점들의 관계를 나타내는 연결선들의 집합으로 표현 : G = (V,E)
  ㅇ [행렬 표현]  인접 행렬 (Adjacency Matrix), 부속/근접 행렬 (Incidence Matrix)
  ㅇ [리스트 표현]  인접 리스트 (Adjaency List)


2. [자료구조]  인접 행렬 (Adjaency Matrix)그래프행렬로 표현하는 방식 중 하나

  ㅇ 그래프행렬 표현 방식의 특징
     - 각 행,열이 정점을 나타내고, 
        . 두 정점(원소) 간의 교차점(원소)에 연결선의 수를 부여
     - 행렬 크기가, n x n 임
        . 즉, 공간 복잡도가, O(n2) 임 

  ㅇ `방향 그래프`의 경우에, 인접 행렬 표현의 例
     - 행렬 원소 값 : 정점들 간에 화살의 개수
        . (만일, 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개의 연결 리스트에 만 나타남

      

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

  ㅇ 특징
     - (효율적 기억장소 활용)
        . 각 연결선 마다 연결 리스트 항목에 하나씩 대응되므로,
        . 존재 않는 연결선을 표현 않게되어, 기억장소 낭비가 적음
     - (각 정점의 이웃 순환이 용이)
        . 각 정점연결 리스트를 따라가기 만 하면 됨


4. [자료구조]  그래프자료구조로써 표현할 때의 유의점그래프는, 노드(정점) 위주의 트리 표현과는 달리, 
     - 주로, 연결선 위주로, 구조 정보의 표현 필요
        . 이때, 주로, 인접 리스트를 많이 사용 (array of adjacency lists)
           .. 연결 리스트를 갖는 배열 구조
     - 다만, 각 노드(정점)는, `명칭(라벨)`,`방문 여부` 정도 만을 유지할 필요 있음
  ㅇ 만일, 그래프를, 클래스 형식으로 표현한다면, 다음 사항들이 항상 추적 가능해야 함
     - 총 노드 갯수는 얼마인가?
     - 각 노드 마다 연결선 갯수는 얼마인가? 등


[그래프] 1. 그래프 2. 그래프 종류 3. 그래프 표현 4. 평면 그래프
[그래프 용어] [그래프 알고리즘]

 
        최근수정     요약목록     참고문헌