본문 바로가기

# Foundation/자료구조

그래프 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

그래프 ADT

유한한 정점(=노드, 점)과 두 정점을 잇는 (=간선, 엣지)으로 정의되는 추상적 자료형.

간선의 특성에 따라 그래프의 종류가 결정된다.

  • 방향성 有.  (Undirected Graph)
  • 방향성 無.  (Directed Graph)
  • 가중치가 있음.  (Weighted Graph)



그래프 ADT의 구현방식

그래프는 전통적으로 2가지의 방식으로 구현할 수 있다.
  • 인접 배열  (Adjacency Matrix)
  • 인접 리스트  (Adjacency List)


구현에 따른 그래프의 성능

  • 인접 배열?
    • 메모리 사용량은 항상 O(n^2)
    • 두 노드간 정보를 조회하는데 O(1)
    • 두 노드간 새로운 간선을 추가하는데 O(1)
    • 새로운 노드를 추가하거나 삭제하는데 (O^2)
    • 모든 간선의 정보를 조회하는데 느림



  • 인접 리스트?
    • 메모리 사용량은 간선의 수에 비례  (노드의 수와는 관계없음)
    • 두 노드간 정보를 조회하는데 O(k)   (k는 이웃노드의 수)
    • 두 노드간 새로운 간선을 추가하는데 O(1)
    • 새로운 노드를 추가하거나 삭제하는데 빠름.
    • 모든 간선의 정보를 빠르게 조회할 수 있음.




특수한 형태의 그래프

  • 희소 그래프  (Sparse Graph)

간선의 수가 굉장히 적은 그래프.



  • 밀집 그래프  (Dense Graph)

간선의 수가 최대 간선의 수에 가까운 그래프.



  • 완전 그래프  (Complete Graph)

간선의 수가 최대 간선의 수와 같은 그래프.




'# Foundation > 자료구조' 카테고리의 다른 글

이진트리 ADT  (0) 2019.02.06
트리 ADT  (0) 2019.02.06
덱 (데크)  (0) 2019.02.04
환형 배열 (원형 배열)  (0) 2019.02.03
큐 ADT  (0) 2019.02.03