인접 행렬(adjacency matrix)이란 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미합니다. 즉, 정사각형 행렬의 각 요소는 1 또는 0 값을 가지는데 0은 두 정점 사이의 경로가 없음을 의미하며 1은 두 정점 사이의 경로가 있음을 의미합니다.
인접 리스트(adjacency list)란?
인접 리스트(adjacency list)는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미합니다.
인접 행렬과 인접 리스트의 차이
공간 복잡도
인접 행렬 : O(V^2)
인접 리스트 : O(V + E)
시간 복잡도 : 간선 한 개 찾기
인접 행렬 : O(1)
인접 리스트 : O(V)
시간복잡도 : 모든 간선찾기
인접 행렬 : O(V^2)
인접 리스트 : O(V + E)
인접 행렬과 인접 리스트 사용해야 할 때
그래프가 희소(sparse)할 때는 모든 간선에 대해서 2차원 배열로 미리 생성해야 하는 인접 행렬보다는 인접리스트를 사용하는 것이 좋습니다.
그래프가 조밀(dense)할 때는 인접 행렬이 인접 리스트보다 좋습니다. 메모리 효율성은 동일한 반면에 정점 i에서 정점 j까지의 간선을 확인하는 속도가 더 빠르기 때문에 인접 행렬을 사용하는 것이 좋습니다.
