그래프 표현

(2020-01-02)

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

1. 그래프의 표현 

  ㅇ [일반적 표현]  그림으로 나타냄
  ㅇ [수학(집합) ]  정점들의 관계를 나타내는 연결선들의 집합으로 표현 : G = (V,E)
  ㅇ [컴퓨터 표현]  (행렬) 인접 행렬(Adjacency Matrix), (자료구조) 인접 리스트


2. 인접 행렬 (Adjaency Matrix)그래프행렬로 표현한 것

  ㅇ 방향 그래프의 인접 행렬 표현 例
     - 행렬 원소 값 : 정점들 간에 화살의 개수
     
        . v1 자신 간에 화살 1개
        . v1에서 v2로의 화살 0개
        . v2에서 v3로의 화살 2개

     - 특징
        . 타 정점을 가리키는 정점인 경우에 만 값(연결 관계)이 부여됨

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

     - 특징
        . 대칭 : 대칭 행렬의 형태를 갖음
        . 차수 : 행 또는 열을 합해 얻은 수와 같음


3. 인접 리스트 (Adjaency List)그래프의 각 정점들을 연결 리스트(Linked List)로 표현한 것
      


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

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