그래프
그래프란 객체 간에 짝을 이루는 관계를 정점(Vertice)와 간선(Edge)으로 나타내는 수학구조이다.
예를 들면, 아래와 같이 대한민국의 도시들의 고속도로 연결관계를 그래프 구조로 나타낼 수 있다.
그래프는 아래와 같은 수식으로 나타낸다.
G = ( V , E )
V는 정점(Vertice), E는 간선(Edge)를 나타낸다. 위 그래프는 7개의 정점과 9개의 간선을 가진 그래프이다.
이제 그래프 구조를 자료구조로 나타내보자.
그래프를 표현하는 방법으로는 인접 행렬 표현법, 인접 리스트 표현법이 있다.
인접 행렬 표현법
그래프의 연결 정보를 행렬로 저장하는 방법이다. 아래와 같이 세로축, 가로축에 각 도시 이름을 기록하고, 교차하는 곳에 도시를 연결하는 고속도로의 존재 여부를 표기한다. 고속도로가 있다면 1, 없다면 0을 기록하면 된다. 행렬의 크기는 정점(V)의 제곱이 된다. 따라서 간선이 많은(=높은 밀도의) 그래프의 표현 시 사용된다.
* 위와 같이 간선의 방향성이 없는 경우를 무방향 그래프라고 한다. 무방향 그래프는 인접 행렬로 표현했을 때 대칭이 되므로, 반만 저장하여 메모리 효율을 높일 수 있다.
인접 리스트 표현법
그래프의 연결 정보를 리스트로 저장하는 방식이다. 도시 길이만큼의 배열을 만들고, 각 도시에 연결된 도시들을 리스트로 저장한다. 이때 저장되는 도시들의 수는 (간선의 총 개수 * 2) 이다. 즉, 2 * E만큼의 메모리를 사용한다. 따라서 정점의 개수에 비해 간선의 개수가 적은(=낮은 밀도의) 그래프의 표현 시 사용된다.
* 인접 리스트 표현은 무방향/방향 그래프 모두 메모리 사용이 동일하다.
이렇게 저장된 데이터를 사용하여 원하는 최댓값/최소값을 구하는 데 사용되는 알고리즘이 BFS, DFS이다. 해당 알고리즘에 대한 정보는 아래 글에 있다.