Graph 문제 풀이시 인접 행렬(Adjacency Matrix) 과 인접 리스트(Adjacency List) 사용 장단점

1. 인접 행렬 (Adjacency Matrix)

• 정의:
  정점의 수가 V일 때, V×V 크기의 2차원 배열을 사용하여 간선의 존재 유무 또는 가중치를 표시합니다.

장점

• 간선 존재 여부 확인이 빠름: O(1) 시간 복잡도로 graph[u][v]를 통해 즉시 확인 가능.
• 구현이 간단하고 직관적: 특히 가중치가 있는 그래프에서 직관적으로 표현 가능.
• 무방향 그래프에서는 대칭 행렬로 표현할 수 있어 깔끔함.

단점

• 공간 복잡도가 높음: 간선 수가 적은 희소 그래프(sparse graph)에서는 메모리 낭비가 큼. 공간 복잡도는 O(V^2).
• 모든 인접 노드를 탐색할 때 비효율적: 연결 여부가 0이더라도 모든 노드를 순회해야 해서 O(V) 시간 소요.

활용 사례

• 정점 수가 작고 간선 수가 많은 조밀한 그래프(Dense Graph).
• 간선 존재 여부를 자주 확인해야 하는 경우.
• 플로이드–워셜 알고리즘 같은 모든 정점 간 최단거리 알고리즘에 적합.

 

2. 인접 리스트 (Adjacency List)

• 정의:
  각 정점마다 연결된 정점들을 리스트(혹은 벡터, 링크드 리스트 등)로 저장합니다.

장점

• 공간 효율성 우수: 간선 수 E에 비례하는 공간 사용. 공간 복잡도는 O(V + E).
• 인접 노드 순회가 효율적: 리스트만 순회하면 되므로 O(degree(v)) 시간.

단점

• 간선 존재 여부 확인이 느림: 특정 간선이 존재하는지 확인할 때는 리스트를 순회해야 하므로 O(degree(v)) 시간.
• 구현이 조금 더 복잡: 가중치를 표현할 경우 (정점, 가중치) 형태로 저장해야 함.

활용 사례

• 정점은 많고 간선이 적은 희소 그래프(Sparse Graph).
• DFS, BFS, 다익스트라 등의 탐색 및 최단 경로 알고리즘.
• 실제 네트워크, 소셜 그래프 등 현실적인 큰 그래프 모델링.

 

비교 요약

항목	인접 행렬	인접 리스트
공간 복잡도	O(V^2)	O(V + E)
간선 존재 여부 확인	O(1)	O(degree(v))
인접 노드 순회	O(V)	O(degree(v))
구현 난이도	쉬움	중간
적합한 그래프	조밀 그래프 (Dense)	희소 그래프 (Sparse)