LIME이번 포스팅에서는 그래프(Graph)에 대해 정리하고자 합니다.
그래프(Graph)란?
그래프란 노드(Node)와 간선(Edge)으로 구성된 비선형 데이터 구조입니다.
즉 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조를 의미합니다.
그래프 용어
- 노드(Node): 그래프의 기본 요소로, 데이터를 저장하는 역할을 한다, 동그라미로 표현.
- 간선(Edge): 노드와 노드를 연결하는 선, 화살표로 표현.
- 가중치(Weight): 관계나 흐름에서 정도를 나타냄, 간선 위에 숫자로 표현.
그래프의 특징과 종류
그래프는 크게 방향성, 가중치, 순환에 따라 종류를 구분할 수 있습니다.
- 방향성(Directed): 간선은 방향을 가질 수도 있고 그렇지 않을 수도 있습니다. 방향이 있는 간선을 포함하면
방향 그래프, 방향이 없는 간선을 포함하면무방향 그래프라고 합니다. - 가중치(Weight): 가중치는 흐름의 방향 뿐만 아니라 양을 나타냅니다. 가중치가 있는 간선을 포함하면
가중치 그래프라고 합니다. - 순환(Cyclic): 순환은 특정 노드에서 시작해 간선을 따라 다리 돌아오는 경로가 있는 것을 의미합니다. 순환이 존재하면
순환 그래프, 순환을 포함하지 않는다면비순환 그래프라고 합니다.
그래프의 구현
그래프의 구현 방식은 인접 행렬과 인접 리스트가 있습니다.
인접행렬 그래프 표현
인접행렬은 노드 간의 관계를 2차원 배열로 표현하는 방법입니다.
배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고,
인덱스의 세로 방향을 출발 노드, 가로 방향을 도착 노드로 생각하면 자연스럽게 그래프를 표현할 수 있습니다.
인접 리스트 그래프 표현
인접 리스트는 노드 간의 관계를 리스트로 표현하는 방법입니다.
적절한 노드를 정의해야 하며 값, 가중치, 다음 노드를 묶어서 관리합니다.
구현 방식에 따른 장단점
두 방식으로 그래프를 표현 할 때 어느 한쪽이 특별히 뛰어난 것은 아니고 각각 장단점이 존재합니다.
인접 행렬의 장단점
인접 행렬은 아래와 같은 2가지 단점이 있습니다.
- 인접 행렬로 희소 그래프를 표현하는 경우 비효율 발생
- 노드들의 값의 차이가 매우 큰 그래프를 표현하는 경우에 가장 큰 노드의 값을 기준으로 행렬의 크기를 잡아야 함
위와 같은 단점이 있지만 아래와 같은 장점도 있습니다.
- 시간 복잡도가 O(1)으로 좋음
- 구현 난이도가 낮음
인접 리스트의 장단점
인접 리스트는 인접 행렬과 정반대의 장단점을 가집니다.
인접 리스트는 아래와 같은 장점이 있습니다.
- 실제 연결된 노드에 대해서만 노드의 값을 노드에 담아 연결하기만 하면 되어서 메모리를 아낄 수 있다.
다만 단점이 존재합니다.
- 연결된 노드 개수가 많으면 많을수록 노드를 연결한 리스트의 길이만큼 탐색해야 해서 탐색 시간이 O(N) 이다.
그래프 문제를 풀 때는 인접 행렬과 인접 리스트 중에서 더 좋은 것을 선택해야 하는데,
보통 시간 제약에서 장점을 취하기 위하여 인접 행렬 방식으로 그래프 문제를 푸는 경우가 많습니다.
문제에서 노드 개수가 1,000개 미만으로 주어지는 경우에는 인접 행렬을 사용하면 됩니다.