자료구조 - Graph

Graph

node와 edge로 구성된 한정된 자료구조이다.

node는 정점이며 edge는 정점 간의 간선이다.

 

그래프는 방향성이 있을 수도, 없을 수도 있다.

인접 리스트

인접 리스트로 그래프를 표현하는 것이 가장 일반적인 방법이라고 한다. 인접 리스트는 그래프 내에 적은 숫자의 간선만을 가지는 경우에 용이하다고 한다. 각각의 정점에 인접한 정점들을 리스트로 표시한 것이다. 배열이나 연결 리스트 등을 이용해서 구현이 가능하다.

 

특징으로는 연결된 간선의 정보만을 저장하여 공간 효율성은 우수하지만 각 정점들의 연결 여부 확인을 위해 O(n)의 시간 복잡도를 가진다.

인접 행렬

인접 행렬은 정점들을 2차원 배열로 나타낸 것이다. 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프의 경우에 용이하다.

 

단점으로는 간선의 수와 무관하게 항상 n^2의 메모리 공간이 필요하다. 또한 특정 노드의 인접 노드를 탐색하기 위해서 모든 노드들을 확인해야 한다.

하지만 정점 간의 연결여부 확인 시 O(1)의 시간 복잡도를 가진다.