[Graph] 인접행렬, 인접리스트 시간복잡도

Node, Edge 개수

인접리스트, 인접행렬 Edge의 개수가 m개 있습니다. Node의 개수는 2m을 의미합니다.

두 개의 Node를 하나의 Edge로 연결합니다.

하나의 연결로 두 개의 Node가 존재하기 때문에 Node 개수는 Edge 개수보다 2배 많은 2m을 의미합니다.

아래 왼쪽 그림의 연한 주황색과 오른쪽 그림 숫자 1은 Node를 의미합니다.

위의 Graph 그림에서 Edge가 5개인 반면 인접 행렬, 리스트의 노드 개수는 10개인 것을 확인할 수 있습니다.

인접 리스트 - 시간복잡도

M = Node의 개수, E = Edge의 전체 개수로 표현

• Node 추가 : O(1)
• Node 삭제 : O(M+E)
• Edge 추가 : O(1)
• Edge 삭제 : O(E)

Node 추가 : 이중연결리스트 꼬리 nextNode로 지정하기 때문에 상수 시간만큼 소요됩니다.

Node 삭제 : 노드를 삭제하면 삭제된 공간을 채우기 위해 다시 색인하는 과정이 필요하므로 노드, 정점의 개수를 합한 만큼의 시간이 소요됩니다.

Edge 추가

Edge 삭제 : 최악의 상황은 한 줄로 노드가 연결되어 있는 경우입니다. 삭제하기 위해 마지막 Edge까지 탐색해야 합니다.

인접 행렬 - 시간복잡도

M = Node의 개수, E = Edge의 전체 개수로 표현

• Node 추가 : O(M^2)
• Node 삭제 : O(M^2)
• Edge 추가 : O(1)
• Edge 삭제 : O(1)

Node 추가 : 행과 열을 모두 추가해야 하므로 노드 개수의 제곱만큼의 시간이 필요합니다. 추가로 새로 생긴 행과 열에 대한 각 셀을 채워야 합니다.

Node 삭제

Edge 추가 : Edge 추가는 특정 셀의 값만 변경(0, 1)하면 되므로 상수 시간만큼 소요됩니다.

Edge 삭제 : Edge 삭제는 특정 셀의 값만 변경(0, 1)하면 되므로 상수 시간만큼 소요됩니다.

비교

상대적으로 인접리스트는 Node의 추가, 삭제가 빈번하게 발생하는 경우 사용하는 것이 좋습니다.

상대적으로 인접행렬은 Edge의 추가, 삭제가 빈번하게 발생하는 경우 사용하는 것이 좋습니다.