도입

스택, 큐와 같은 자료구조들은 선형으로 구성된 자료들을 컴퓨터 프로그램으로 표현하는데에 사용됩니다. 하지만, 여러 도시들의 연결망, 사람들간의 사회적 관계 등을 표현하기 위해서는 적합하지 않다는 단점이 있습니다. 이러한 자료들을 표현하기 위해서, 그래프라는 자료구조를 사용합니다.

그래프 개요

그래프의 정의

전산학에서 말하는 그래프는 수학시간에 그렸던 함수의 그래프랑은 다른 물건입니다. 그래프 자료구조는 어떤 자료나 개념을 표현하는 정점(Vertex)와, 이들을 연결하는 간선(Edge)들의 집합으로 구성됩니다. 그 외의 정점의 위치나, 간선의 순서 같은것은 정의에 포함되지 않습니다.

그림1 : 그래프의 예시. 위의 그래프에는 간선(edge)에 비용을 적어놓은 예시이다

그래프의 종류

그래프의 정의는 위와 같이 간략하게 나타낼 수 있습니다만, 간선과 정점들에 특정한 속성들을 붙여서 여러 종류로 만들어서 사용하기도 합니다. 가장 대표적인것은, 정점들을 연결하는 간선에 방향을 부여하여, 방향 그래프(directed graph)와, 무향 그래프(undirected graph)로 구분할 수 있고, 간선을 이용하는 비용이 다 같느냐(다르게 말하면, 정점간의 거리가 같냐)에 따라서, 가중치 그래프냐 아니냐를 구분하기도 합니다.
그래프의 형태로도 그래프의 종류를 구분하기도 합니다. 정점들 사이에 2개 이상의 간선이 있을 수 있는 다중그래프(multigraph), 그래프의 정점들을 두 그룹으로 만들어서, 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하는 이분 그래프(bipartie graph) 등등으로 나누기도 하는데, 이들의 이름을 외우는것은 그렇게 중요한 일이 아닙니다. 그래프 관련 알고리즘을 배우면서, 처음 보는 용어가 나왔을 때, 구글에 찾아보는것으로도 충분합니다.

그래프의 경로

그래프에서 중요하게 다뤄지는 개념중 하나는 경로(path)입니다. 경로의 사전적 정의는 끝과 끝이 연결된 간선을 서로 연결한 것입니다.

그림 2 : 방향 그래프의 한 예

위의 그림에서 (0,1), (1,2), (2,3), (3,4)는 끝과 끝이 이어진 간선이므로, 하나의 경로를 이룹니다. 앞으로는 거쳐가는 정점의 번호만으로 간략히 기재하도록 하겠습니다.
방향 그래프에서는 앞 간선의 끝점이 뒷 간선의 시작점과 만나야 합니다. 따라서 0-1-3-4 는 경로로 볼 수 없습니다.(1에서 3으로 가는 간선이 없기 때문입니다)

경로 중 한 정점을 여러번 거치지 않는 경로를 단순 경로(simple path)라고 합니다. 예를 들어서 1-2-3-1-4 는 1번 정점을 두번 지나가기 때문에 단순 경로가 아닙니다. 그리고, 대부분 알고리즘에서 경로라고 하면, 대부분 단순경로를 의미하고, 한 정점을 여러번 거칠 수 있다면 그것을 별도로 명시합니다.

추가로 시작한 점에서 끝나는 경로를 사이클(cycle)이라고 합니다. 위 그림에서 0-1-2-3-4-0은 0에서 출발하여 0에서 끝나는 경로이며, 사이클을 이룹니다.

그래프의 표현방법

그래프의 정의를 이제 알게 되었으니, 실제 코드에서 이를 어떻게 표현하는지 알아봅시다. 그래프는 다른 자료구조와는 다르게, 삽입과 삭제가 빈번히 일어나지 않는 경우가 많기 때문에, 좀 더 간단하고, 메모리를 적게 표현하는 방법으로 표현하는 경우가 많습니다. 크게 두가지 방법으로 나누어 집니다.

인접 리스트 표현

첫번째 표현은 그래프의 각 정점마다 해당 정점에서 나와서 어느 정점으로 갈 수 있는지를 리스트의 형태로 표현하는 것입니다. C++로는 아래와 같은 형태로 구현을 할 수 있겠죠

vector<list<int> >adjacent;

이때 adjacent[i]는 i 정점에서 간선을 통해 갈 수 있는 정점들의 정보를 저장하는 연결 리스트 입니다. 만약에 간선에 가중치등의 추가적인 속성이 붙는다면, int 만이 아니라, 간선의 정보를 담은 구조체나, pair<int,int>등의 방법을 이용해서 그 정보또한 담을 수 있겠죠.

인접 행렬 표현

첫번째로 소개한 인접 리스트 표현 방식의 가장 큰 단점은 두 정점이 주어졌을 때, 두 정점이 연결되었는지 확인하려면 연결리스트를 일일히 뒤져서 시간이 좀 걸린다는 점입니다. 이런 연산의 속도를 높히기 위해서 고안된 그래프 표현 방식이 인접 행렬 표현입니다.
그래프의 인접 행렬 표현 방식은, $|V| \times|V|$크기의 행렬, 즉 이차원 배열에 두 정점의 연결정보를 저장하는 방법입니다.
단지 두 정점이 연결되어 있는지 아닌지를 저장하는 간단한 구현은 아래와 같습니다.

vector<vector<bool> > adjacent;

간선에 정보가 추가로 있는 가중치 그래프 등을 표현하기 위해서는 bool변수 대신에, 가중치를 나타내는 int변수나 ,double등의 실수형을 사용할 수 있겠지요

두 방식의 장단점 비교

이 두 방식은 특성이 서로 정반대여서, 한 방식의 장점이 다른 방식의 단점이 되기 때문에, 한 방식만 고집하기 보다는, 구현하고자 하는 문제상황의 성질에 맞추어서 표현 방식을 선택하는것이 중요합니다.

간단히 표현하자면, 인접 행렬 표현은 메모리를 좀더 많이 쓰는 대신, 두 정점이 연결되었는지 확인하는 속도가 빠릅니다.

반면, 인접 리스트 표현은 메모리를 덜 쓰는 대신에 두 정점의 연결 여부를 확인하는데에 좀 더 시간이 걸리지요.

메모리 사용의 차이는 정점에 비해서 간선이 작은 희소 그래프(sparse graph)에서 확연히 볼 수 있습니다.

그림 3 : 밀집 그래프와 희소 그래프의 비교

왼쪽의 밀집 그래프와 오른쪽의 희소 그래프는 정점의 개수는 같고, 간선의 개수만 다릅니다. 정점의 개수가 $V$이고, 간선의 개수가 $E$일때, 인접 행렬 방식이 소모하는 메모리는 간선과는 상관없이 $O(V^2)$이고, 인접 리스트 방식은 $O(V+E)$ 입니다.

이렇게 그래프의 표현방식은 알고리즘의 시간복잡도를 결정할 수 있는 중요한 요소이기 때문에 신중하게 결정해야 합니다.

암시적 그래프 표현

그래프를 이용해서 푸는 문제를 풀 때, 위와 같은 방법으로 문제의 입력 데이터를 가공해서 풀 수 있지만, 암시적인 그래프 표현을 이용해서 문제를 풀 수 있습니다. 간단한 예로, 이동할 수 있는 통로와, 이동할 수 없는 벽이 0과 1로 주어지는 문제 상황에서, 주어지는 칸에 정수 일련번호를 매기고 그 칸들의 연결관계를 그래프로 나타낼 수 있겠지만, 해당하는 칸의 상하좌우가 벽인지 아닌지 판별하여, 탐색을 해나갈 수 있겠습니다.

이 방법이 가장 큰 효과를 발휘할 때는, 큰 그래프 에서 일부분만 처리할 때 입니다. 15-퍼즐이 대표적인 예인데, 15개의 조각과 1개의 빈칸을 배치하는 방법은 $16!$이며, 이는 약 20조 정도 되는 매우 큰 수 입니다. 하지만, 실제로 15-퍼즐 문제를 해결할 때에는 조각 하나를 움직이는 4가지 종류의 상태 정도만 방문하기 때문에, 모든상태를 그래프로 표현하는것은 실용적이지 못하고, 암시적 그래프 표현 구조를 이용함으로 메모리를 절약하는 효과를 기대할 수 있겠습니다.

하지만 이 방식이 만능이라는 것은 아닙니다. 암시적 그래프 표현을 사용하면, 그래프의 변환 과정과 본래의 알고리즘이 합쳐지게 되어 그 과정에서 코드가 더 복잡해지게 되고, 이는 코드 짬에 있어서 실수로 다가오게 됩니다. 그래프에 대해서 복잡한 연산을 해야 할 때는, 주어진 입력을 그래프 구조로 온전히 변환해서 하는것이 좋겠습니다.