그래프(Graph)
그래프는 자료구조 중 하나로 노드(Node, 정점)와 에지(Edge, 간선)로 구성된 집합으로 비선형 자료 구조이다.
노드는 데이터를 표현하는 단위고 에지는 노드를 연결해 준다.
언뜻 보면 그래프와 트리가 비슷하게 보일 수 있는데 차이점으로는 그래프는 사이클이 발생하지만, 트리는 사이클이 발생하지 않는다는 차이가 있다.
그래프의 종류
그래프 자료구조는 다양한 형태를 가지고 있는데 그중에서 간단하게 3개만 살펴보자.
무방향 그래프
무방향 그래프는 말 그대로 정점을 이어주는 간선에 방향성이 없는 그래프로 순서가 지정되지 않은 쌍이다.
무방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi , Vj)로 표현하는데 방향이 없기 때문에 (Vi , Vj)와 (Vj , Vi)는 같은 간선이다.
방향 그래프
무방향 그래프와는 다르게 방향 그래프는 정점을 이어주는 간선에 방향이 있는 그래프이다.
정점 Vi와 Vj를 연결하는 간선을 (Vi , Vj)로 표현하면 간선에 방향이 있기 때문에 (Vi , Vj)와 (Vj , Vi)는 서로 다른 간선이다.
가중치가 있는 그래프
가중 그래프라고도 불리며 정점을 연결하는 간선에 가중치를 할당한 그래프 형태이다.
가중치는 일종의 다른 노드로 가기 위한 비용으로 이를 이용하여 거리를 구하거나 최단 경로를 구할 때 사용할 수 있다.
그래프의 표현
그래프 표현을 알고 있어야 그래프 자료구조를 어떻게 활용할지 알 수 있다.
그래프를 구현하는 방법은 총 3가지가 있는데 하나씩 살펴보자.
1. 에지 리스트(Edge List)
에지를 중심으로 그래프를 표현하는데 가중치가 있는 경우와 없는 경우가 존재한다.
- 에지 리스트로 가중치 없는 그래프 표현
출발 노드와 도착 노드만 표현하므로 배열의 행은 2개면 충분하다.
※ 방향이 없는 그래프가 나오면 시작과 종료 노드를 설정하지 않거나, 처음부터 서로 넣어주면 된다.
- 에지 리스트로 가중치 있는 그래프 표현하기
그래프 행을 3개로 늘려주면 된다. (시작과 종료 가중치로 행을 구성하면 된다.)
에지 리스트의 단점으로 특정 노드와 관련되어 있는 에지를 탐색하기는 쉽지 않다. (특정 노드를 알기 위해 데이터를 전부 탐색하여 찾아야 한다.)
벨만 포드나 크루스칼 알고리즘에 사용하고, 노드 중심 알고리즘에는 잘 사용하지 않는다.
2. 인접 행렬(Adjacency Matrix)
2차원 배열을 자료구조로 이용하여 그래프를 표현한다.
인덱스를 이용해서 시작 노드와 종료 노드를 표현한다.
인접 행렬을 이용하면 그래프를 구현하기 쉽고 두 노드를 연결하는 에지의 여부와 가중치 값은 배열에 직접 접근하면 바로 확인할 수 있는 것도 장점이다.
단점으로 노드와 관련되어 있는 에지를 탐색하려면 N번 접근해야 하므로 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어진다. 위의 사진과 같이 2번 인덱스에 관련된 에지를 찾기 위해서는 1~5번 에지까지 탐색을 거쳐야 되기 때문에 탐색 속도가 느려지고 에지와 관련 없는 빈 값이 많이 발생하기 때문에 공간 효율성이 떨어진다.
인접 행렬을 효율적으로 적용하기 위해서는 노드가 굉장히 적을 때 사용하는 것이 좋다.
따라서, 인접 행렬은 노드 개수에 따라 사용 여부를 적절하게 판단하는 것이 중요하다.
- 인접 행렬로 가중치 없는 그래프 표현하기
시작 노드에서 도착 노드에 도달할 시 1을 저장해서 표현한다.
1을 저장하는 이유는 가중치가 없기 때문에 에지가 있다는 표시를 위해 1로 설정한다. (T/F도 가능)
- 인접 행렬로 가중치 있는 그래프 표현하기
시작 노드에서 도착 노드에 도달할 시 가중치를 저장해서 표현한다.
3. 인접 리스트
코딩 테스트에 사용하는 경우가 많고, ArrayList로 그래프를 표현한다. (ArrayList를 이용하는 이유는 길이가 가변적이기 때문이다.)
ArrayList를 이용하여 표현하기 때문에 배열의 장점인 인덱스에 직접 접근이 가능하고, 리스트를 통해 연결된 노드를 확인할 수 있다. (배열의 장점 + 리스트의 장점)
- 인접 리스트로 가중치 없는 그래프 표현하기
- 인접 리스트로 가중치 있는 그래프 표현하기
가중치가 있는 인접 리스트를 표현할 때 Node 클래스를 만들어 사용해야 한다. (Node 클래스에는 종료 노드와 가중치가 있다.)
인접 리스트를 사용하는 이유는 그래프 구현은 복잡하지만, 노드와 연결되어 있는 에지를 탐색하는 시간이 매우 뛰어나다.
인접 행렬은 어쩔 수 없이 목표 노드에 접근하려면 탐색이 필요하지만 인접 리스트는 탐색이 필요하지 않기 때문에 공간 효율이 좋아 인접 행렬에서 발생할 수 있는 메모리 초과 에로도 발생하지 않는다.
위 사진과 같이 인접 행렬에서 2번 인덱스에 접근하여 해당 인덱스와 연관된 에지를 찾기 위해서는 모든 탐색 과정을 거쳐야 에지 가중치인 4와 15를 찾을 수 있지만, 인접 리스트는 2번 인덱스에 접근하면 곧바로 해당 인덱스와 관련된 에지와 가중치를 확인할 수 있다.
그래프 자료구조의 장단점
그래프 자료구조의 장점
다양한 관계와 자료구조를 직관적으로 표현하는 데 사용된다.
길 찾기, 데이터 클러스터링, 네트워크 분석 및 기계 학습을 포함한 광범위한 문제를 모델링하고 해결하는 데 사용할 수 있다.
그래프 알고리즘은 대개 매우 효율적이며 복잡한 문제(최단 경로, 최소 신장 트리 등)를 빠르고 효과적으로 해결하는 데 사용할 수 있다.
그래프 데이터 구조를 사용하면 복잡한 데이터 구조를 간단하고 직관적인 방식으로 표현하여 이해하고 분석하기가 더 쉽다.
그래프 자료구조의 단점
그래프 자료구조는 특히 그래프 이론이나 관련 알고리즘에 익숙하지 않은 사람들에게는 복잡하고 이해하기 어려울 수 있다.
매우 크거나 복잡한 그래프의 경우 그래프를 생성하거나 탐색하는 비용이 증가한다.
그래프 데이터 구조는 시각화하고 분석하기 어려울 수 있으며 특히 매우 크거나 복잡한 그래프의 경우 데이터에서 의미 있는 통찰력을 추출하기 어려울 수 있다.
'CS > 자료구조' 카테고리의 다른 글
| 자료구조 - AVL 트리 (0) | 2023.12.10 |
|---|---|
| 자료구조 - 이진 트리(Binary Tree) (0) | 2023.08.16 |
| 자료구조 - 트리(Tree) (0) | 2023.08.16 |
| 자료구조 - 스택과 큐 (0) | 2023.08.06 |
| 자료구조 - 배열과 리스트 (0) | 2023.08.05 |
