[javascript] 그래프 표현 방식 (Graph Representation) 데이터 구조
그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 데이터 구조이다. 그래프는 현실 세계의 다양한 관계를 모델링하는 데 사용되며, 컴퓨터 과학 분야에서도 다양한 알고리즘에 활용된다.
이 포스트에서는 그래프를 효과적으로 표현하는 여러 방식들을 살펴보겠다.
1. 인접 행렬 (Adjacency Matrix)
인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방식이다. 그래프의 모든 정점을 행과 열에 대응시키고, 해당하는 정점들 사이에 간선이 존재하는지를 나타낸다. 만약 두 정점 사이에 간선이 존재한다면 1로 표시하고, 간선이 존재하지 않는다면 0으로 표시한다.
// 예시 인접 행렬
const graph = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 0],
[0, 1, 0, 0]
];
인접 행렬은 간선의 존재 여부를 빠르게 확인할 수 있지만, 그래프의 크기가 커질수록 메모리 공간을 낭비할 수 있다.
2. 인접 리스트 (Adjacency List)
인접 리스트는 배열의 배열 또는 링크드 리스트를 사용하여 그래프를 표현하는 방식이다. 각 정점에 연결된 정점들의 리스트를 저장한다.
// 예시 인접 리스트 (배열의 배열)
const graph = [
[1, 2],
[0, 2, 3],
[0, 1],
[1]
];
인접 리스트는 메모리를 효율적으로 사용할 뿐만 아니라, 인접한 정점을 효율적으로 탐색할 수 있다. 하지만 간선의 존재 여부를 확인하는 데에는 추가적인 시간이 소요된다.
결론
그래프를 효율적으로 표현하는 방법은 해당 그래프의 특성에 따라 다를 수 있다. 인접 행렬은 간선의 존재 여부를 빠르게 확인할 수 있지만, 메모리를 많이 차지한다. 반면 인접 리스트는 메모리를 효율적으로 사용하며, 인접한 정점을 효율적으로 탐색할 수 있다.
따라서 그래프를 효과적으로 다루기 위해서는 해당 그래프의 특성과 요구사항을 고려하여 적합한 방식을 선택해야 한다.