그래프 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)

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