- 그래프란?
그래프 : 노드와 간선을 이용한 비선형 데이터 구조
그래프를 구성하는 용어들을 정리해보자.
그래프는 데이터 간의 관계를 표현하는 데에 사용하며,데이터를 노드로, 데이터 간의 관계나 흐름을 간선으로 표현하는 특징을 갖는다.간선은 방향을 가질 수도 있고 갖지 않을 수도 있다.또한 관계나 흐름에서 정도를 표현할 때에는 가중치라는 개념을 사용한다.
그림 속 예시을 통해 노드, 간선, 가중치라는 용어를 알아보자.
그림에서 동그라미로 표현한 것이 노드, 화살표로 표현한 것이 간선, 간선 위에 숫자로 표현한 것이 가중치이다.
그래프의 특징과 종류에 대해 알아보자.
그래프는 방향성, 가중치, 순환의 특성에 따라 종류를 구분할 수 있다.
1. 흐름을 표현하는 방향성의 유무 : 방향 그래프(directed graph), 무방향 그래프(undirected graph)
2. 흐름의 정도를 표현하는 가중치의 유무 : 가중치 그래프(weighted graph)
3. 시작과 끝의 연결 여부를 보는 순환의 유무 : 순환 그래프(cycle graph), 비순환 그래프(acyclic graph)
그래프의 구현에 대해 알아보자.
그래프의 구현 방식에는 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)가 있다.
1. 인접 행렬로 그래프 구현하기
구현 방법의 설명을 위해 서울에서 부산까지 400km가 걸린다는 내용을 그래프로 표현하고자 한다.
- 노드 : 데이터를 담고 있음 (서울, 부산)
- 간선 : 노드를 잇는 선 (서울과 부산의 연결 유무)
- 방향 : 간선의 방향 (서울에서 부산 방향으로)
- 가중치 : 간선의 가중치 (400km)
세로 방향 인덱스를 출발, 가로 방향 인덱스를 도착으로 하여 서울(0) -> 부산(1)로 향하는 가중치가 400인 그래프 구현
( -로 표현한 가중치는 실제 코드에서는 -1로 지정한다. )
2. 인접 리스트로 그래프 구현하기
인접 리스트로는 어떻게 그래프를 구현할 수 있을까?
다음과 같이 값(v), 가중치(w), 다음 노드(next)를 묶어서 표현한다.
인접 리스트로 그래프를 구현하기 위해서는 다음과 같은 과정으로 동작한다.
- 노드 개수만큼 배열을 준비한다.
- 배열의 인덱스는 각 시작노드를 의미하며, 배열의 값에는 다음 노드를 연결한다.
그림을 통해 자세히 살펴볼 수 있다.
인접 행렬과 인접 리스트 중 매우 뛰어난 방법이 있는 것은 아니며, 둘은 극명한 장단점이 있다.
인접 행렬의 경우 크게 두 가지 단점이 있다.
첫 번째로는 인접 행렬로 희소 그래프를 표현하는 경우이다. 희소 그래프란 노드 수에 비해 간선 수가 매우 적은 그래프이다. 인접 행렬은 그 크기가 고정되어있으므로 간선 수가 적다면 인접 행렬 공간 중 대부분의 공간은 실제로 사용하지 않으므로 비효율적이다.
두번째 단점은 노드들의 값의 차이가 매우 큰 그래프를 표현하는 경우이다. 예를 들어 노드 값이 1, 2, 77, 999와 같이 간격이 큰 그래프의 경우 가장 큰 노드의 값인 999를 기준으로 인접 행렬의 크기를 잡기에 이 또한 비효율적이다.
장점은 간선 정보를 확인할 때의 시간 복잡도가 O(1)이라는 것이다. 인접 행렬에서는 인덱스 임의 접근으로 노드 간 간선 정보를 바로 확인할 수 있기 때문이다. 예를 들자면 2에서 93으로 가는 간선을 확인할 경우 array[2][93]의 가중치를 확인하면 된다.
구현 난이도가 낮다는 것도 장점이다.
인접 리스트는 인접 행렬과 정반대의 장단점을 가진다.
먼저 장점으로는 실제 연결된 노드에 대해서만 연결하기에 메모리를 아낄 수 있다는 것이다.
하지만 간선 정보를 확인할 때는 특정 노드에서 시작하여 연결된 노드 개수가 많을 수록 그 연결된 길이만큼 탐색해야하므로 시간 복잡도가 O(N)으로 모두 탐색을 해야한다는 것이 단점이다.
