그래프 표현 방식 (인접 행렬 vs 인접 리스트)

그래프 표현 방식 (인접 행렬 vs 인접 리스트)

그래프의 정점과 간선 정보를 메모리에 저장하는 방식으로, 인접 행렬(2D 배열)과 인접 리스트(연결 리스트 배열)가 대표적이며 그래프의 밀도와 연산 패턴에 따라 선택

특징: 공간 복잡도·간선 확인·순회 시간이 방식에 따라 크게 상이

인접 행렬 (Adjacency Matrix)

• •V×V 크기의 2차원 배열, A[i][j] = 1(또는 가중치)이면 간선 존재
• •공간: O(V²), 간선 확인: O(1), 인접 정점 탐색: O(V)
• •무방향 그래프: 대칭 행렬(상삼각만 저장 가능, 공간 절반)
• •장점: 간선 존재 여부 O(1) 확인, 구현 단순, 연속 메모리(캐시 효율)
• •단점: 희소 그래프에서 공간 낭비, 정점 추가 시 배열 재할당

인접 리스트 (Adjacency List)

• •각 정점마다 연결된 정점의 리스트(연결 리스트 또는 동적 배열) 유지
• •공간: O(V+E), 간선 확인: O(degree(v)), 인접 정점 탐색: O(degree(v))
• •장점: 희소 그래프에서 공간 효율, 정점/간선 추가 용이, 대부분의 알고리즘에 적합
• •단점: 간선 존재 확인 O(degree), 포인터 기반(캐시 비효율)

간선 리스트 (Edge List)

• •모든 간선을 (u, v, weight) 튜플의 배열로 저장
• •공간: O(E), 간선 순회에 적합, Kruskal 알고리즘에 활용

적합한 상황

• •밀집 그래프(E ≈ V²): 인접 행렬 (공간 차이 적고 O(1) 접근 이점)
• •희소 그래프(E << V²): 인접 리스트 (공간 O(V+E)로 절약)
• •간선 중심 처리: 간선 리스트 (정렬 후 탐욕 알고리즘)

비교

연관: 그래프, DFS, BFS, 최단 경로 알고리즘, MST