그래프 표현방식 중 인접 행렬과 인접 리스트의 장단점을 서로 비교하며 설명해 주세요. 어떤 경우에 무엇을 사용하는 것이 더 유리한지를 중점으로 설명해주시면 됩니다.

[SW-H]

1. 인접 행렬

인접 행렬이란 그래프의 정점을 2차원 배열로 만든 것이다.

정점 간에 직접 연결되어 있다면 1 , 아니라면 0 을 저장한다.

위와 같은 그래프가 있다면 인접 행렬은 다음과 같이 작성할 수 있다.

장점

1. 2차원 배열에 모든 정점의 간선 정보가 담겨있기 때문에 두 정점에 대한 연결을 조회할 때는 $O(1)$ 의 시간 복잡도를 가진다.
2. 인접 리스트에 비해 구현이 쉽다.

단점

1. 모든 정점에 대해 간선 정보를 입력해야 하므로 인접 행렬을 생성할 때는 $O(n^2)$ 의 시간 복잡도가 소요된다.
2. 항상 2차원 배열이 필요하므로 필요 이상의 공간이 낭비된다.

2. 인접 리스트

인접 리스트는 그래프의 노드를 리스트로 표현한 것이다. 주로 정점의 리스트 배열을 만들어서 관계를 설정한다.

장점

1. 정점들의 연결 정보를 탐색할 때 $O(n)$ 시간 복잡도가 소요된다. (n 은 간선의 갯수)
2. 필요한 만큼 공간을 사용하기 때문에 인접 행렬에 비해 상대적으로 공간의 낭비가 적다.

단점

1. 특정 두 정점이 연결되어 있는지 확인하기 위해서는 인접 행렬에 비해 시간이 오래 걸린다.
2. 구현이 인접 행렬에 비해 어렵다.

인접 리스트와 인접 행렬 중 선택 방법

• 인접 리스트

  • 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프(Sparse Graph) 의 경우
  • 모든 엣지 / 특정 엣지를 조사하는 경우

• 인접 행렬

  • 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph) 의 경우
  • 두 노드간의 연결 여부를 조사해야 하는 경우

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

[anuu0916]

출처 : https://suyeon96.tistory.com/32