[자료구조] 인접행렬 과 인접리스트

📘 자료구조 노트

그래프관련 문제를 풀 때 문제에 조건에 맞게 그래프를 구현하고 푸는게 일반적입니다.

이 때, 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다.

 

인접행렬

이와 같은 그래프가 있다고 했을 때 인접 행렬은

다음과 같은 대칭 행렬 형태로 표현됩니다.

그러므로

꼭짓점의 개수를 n이라고 할 때 인접 행렬은 O(n^2)의 공간 복잡도 를 갖습니다.

인접행렬의 특징

• 원소에 접근하는데 걸리는 시간이 상수 시간(1)이라면 꼭짓점 i에서 j로 가는 변이 있는지를 상수 시간에 알 수 있습니다.(O(1))
• 하지만, 그래프에 존재하는 모든 간선의 수는 O(n^2) 안에 알 수있습니다. 

 

인접 리스트

이와 같은 그래프가 있다고 했을 때 인접 그래프는

다음과 같은 연결 리스트로 표현됩니다.

꼭지점의 개수를 n 간선의 개수를 e라고 할 때 인접 리스트는 O(n+e)의 공간 복잡도를 갖습니다.

인접 리스트의 특징

• 그래프 내에 간선의 숫자가 적은 희소 그래프(Sparse Graph)의 경우 많이 씀
• 그래프에 존재하는 모든 간선의 수는 O(n+e) 안에 알 수있습니다.
• 하지만, 두 정점 사이에 간선으 ㅣ존재 여부는 해당 정점의 차수만큼의 시간이 필요합니다.