복잡한 관계를 데이터로 표현하는 그래프(Graph)의 구현 방식을 정리했다.
노드(Vertex)와 간선(Edge)을 사용하여 연결 상태를 정의한다.
인접 행렬과 인접 리스트 방식을 비교 분석했다.
그래프 구현 방식 (C++)
연결 상태 저장 방식은 크게 두 가지로 구분된다.
// 1. 인접 행렬 (Adjacency Matrix): 2차원 배열 활용
int matrix[MAX][MAX];
matrix[1][2] = 1; // 노드 1과 2의 연결 표시
// 2. 인접 리스트 (Adjacency List): 연결 노드 목록 관리
vector<int> adj[MAX];
adj[1].push_back(2); // 노드 1의 인접 목록에 2 추가
자원 및 성능 비교
-
인접 행렬: 모든 노드 간 관계를 2차원 배열에 기록한다.
연결 여부 확인 속도가O(1)로 빠르나, 노드 수 증가 시 메모리 낭비가 발생할 수 있다. -
인접 리스트: 실제 연결된 노드 정보만 저장한다.
메모리 사용이 효율적이나, 특정 노드 간 연결 확인 시 리스트 탐색이 필요하여 속도가 상대적으로 느리다.
선택 가이드라인
- 인접 행렬: 노드 수가 적고 연결 여부 확인 빈도가 높은 경우에 적합하다.
- 인접 리스트: 간선 수가 적은 희소 그래프(Sparse Graph) 환경이나 메모리 효율이 중요한 경우에 적합하다.
데이터 구조화의 영향
데이터 구조화 방식에 따라 성능과 자원 효율이 결정된다.
문제 특성에 부합하는 그래프 표현 방식을 선택하는 것이 중요하다.
관계 정의 기술을 통해 정교한 코드를 구현할 수 있는 것 같다.
