[알고리즘 이론] 3. 그래프

안녕하세요? 닉네임간편입니다. 이번 시간에는 많이 사용되는 자료구조인 그래프에 대해 알아보겠습니다.

1. 그래프란?

그래프(graph)는 일종의 연결 관계를 나타내는 것으로써, 위 그림처럼 사람 간의 관계나 지하철 노선도 등이 현실에서 사용되는 그래프의 예시입니다. 수직적인 구조가 아니기 때문에 다양한 구조를 표현할 수 있어 많이 사용되는 자료구조입니다.

그래프는 기호로 G(V, E)로 표현되며 이때 V는 정점(vertex)을 의미하고 E는 간선(edge)을 의미합니다. 정점은 어떤 지점을 말하는 것으로, 위 그림에서 사람에 해당됩니다. 간선은 정점을 연결한 선으로, 위 그림에선 점선이 됩니다.

그래프는 정점과 간선들로 구성되어있으며,  정점이나 간선에 가중치 등을 부여해 다양한 방식으로 활용할 수 있습니다.

2. 그래프의 종류

a) 방향 그래프(directed graph)

방향 그래프는 정점을 연결하는 간선에 방향이 있는 것입니다. 위 그림처럼 정점 1에서 정점 2로 간선이 연결될 때 1에서 2로 가는 방향성이 있는 것을 볼 수 있습니다. 도로에서의 일방통행과 정해진 대로 수행해야 하는 제품의 설계도 등이 이에 해당됩니다.

b) 무방향 그래프(== 양방향 그래프, undirected graph)

방향이 없는 그래프이며, 바꿔 말하면 서로를 향해있는 양방향 그래프입니다. 사람 간의 동등한 관계를 예로 들 수 있습니다. 

c) 가중치 그래프(weighted graph)

각 간선에 가중치가 있는 그래프입니다. 예를 들어 서울, 부산, 제주가 정점으로 주어져있다고 할 때, 각 정점으로 가는 데 소요되는 비용과 시간이 다릅니다. 이러한 요소를 가중치로 본다면 이 그래프를 가중치 그래프로 볼 수 있습니다.

d) 트리 혹은 루트 없는 트리(unrooted tree)

순환하지 않는 무방향 그래프의 일종으로, 부모 자식 관계가 없지만 트리와 같은 모양을 띄는 그래프입니다. 순환은 아래에 나오겠지만 순환하지 않는다는 것은 한 정점에서 시작하여 다시 그 정점으로 돌아오지 않고, 간선에 의해 계속해서 다른 정점을 연결한다는 것을 의미합니다. 즉, 두 정점을 잇는 간선이 하나 밖에 없으며 이것들이 나뭇가지처럼 확장됩니다.

3. 그래프의 경로

경로는 정점끼리 이어진 간선들을 순서대로 나열한 것으로, 아래 그림(순환 그래프 그림)을 예시로 들면 5에서 시작한 경로는 5-1-2-3 이 경로가 됩니다.

경로 중 한 정점을 한 번만 지나는 경로를 단순 경로(simple)라고 하며, 대부분 단순 경로를 많이 사용합니다. 아래 그림을 예시로 들면 1-2-4-1-5는 정점 1을 두 번 지나기 때문에 단순 경로가 아니며, 5-1-2-3 은 단순 경로에 해당합니다.

이때 한 정점에서 시작하여 다시 해당 정점으로 돌아오는 경로를 순환 혹은 사이클(cycle)이라고 합니다. 순환 여부에 따라서도 그래프의 종류를 나눌 수 있습니다.

a) 순환 그래프(Cycle graph)

그림을 보면 점정 1에서 시작해서 1 -> 2 -> 4 -> 1로 다시 시작점에 돌아오는 걸 확인할 수 있습니다.

b) 비순환 그래프(Acycle graph)

위 그림처럼 순환하지 않는 그래프를 말합니다.

4. 그래프 표현 방법

그래프는 간선의 정보를 저장하는 방식에 따라 크게 인접 리스트와 인접 행렬로 표현할 수 있습니다.

두 표현 방식은 각각의 장단점이 있기에 필요한 방식을 사용하면 되겠습니다.

a) 인접 행렬(adjacency matrix)

인접 행렬은 V*V의 크기에 해당하는 2차원 배열을 만든 후 여기에 간선 정보를 저장해 그래프를 표현합니다.

장점

배열을 사용하였으므로 두 정점 1과 2가 연결되어있는지 여부를 확인할 때 배열에 한 번만 접근하면 됩니다. 즉, 연결 여부를 확인하는 데 시간복잡도가 O(1)만큼 소요됩니다. 따라서 시간적으론 인접 리스트보다 유용합니다.

단점

V^2의 크기에 해당하는 2차원 배열을 사용하기 때문에 O(V^2)의 공간 복잡도를 가지며, 인접 리스트에 비해 공간을 더 많이 차지합니다. 물론 예외가 존재하긴 하지만, 대게 흔치 않습니다.

b) 인접 리스트(adjacency list)

인접 리스트는 그래프의 각 정점마다 연결된 간선의 목록을 저장해 그래프를 표현하는 방식입니다.

따라서 그래프의 정점은 하나의 연결 리스트를 가집니다.

장점

인접 리스트는 정점과 간선의 개수만큼 공간을 차지하므로 공간 복잡도는 O(V+E)가 됩니다. 따라서 O(V^2)의 공간복잡도를 갖는 인접 행렬에 비해 공간을 덜 차지합니다. 물론 간선의 개수가 V^2개 이상이 된다면 인접 리스트의 공간 복잡도 역시 O(V^2) 이상이 되겠지만, 앞서 말했듯 흔치 않습니다.

간선의 수가 V^2에 가까운 그래프를 밀집 그래프(dense graph)라고 하고, 반대로 V^2에 비해 훨씬 적은 간선의 개수를 가진 그래프를 희소 그래프(sparse graph)라고 합니다. 따라서 밀집 그래프의 경우 인접 행렬을, 희소 그래프의 경우 인접 리스트를 사용하면 되겠습니다.

단점

인접 리스트에서 정점의 연결 여부를 확인하기 위해선 해당 정점의 연결 리스트를 모두 탐색해야 합니다. 따라서 일반적으로 인접 행렬에 비해 시간이 많이 소요됩니다.

c) 결론

즉, 일반적인 경우 인접 행렬은 시간적으로 더 유용하며 인접 리스트는 공간적으로 더 유용합니다. 이렇게 시간적, 공간적 장단점이 각각 상이하기 때문에 이를 고려하여 필요한 표현 방식을 사용하면 되겠습니다.

5. 마무리

이번 시간에는 그래프 자료구조에 대해 알아보았습니다. 이제 그래프를 이용하여 깊이 우선 탐색(DFS)를 하거나 너비 우선 탐색(BFS)을 할 수 있습니다. 다음 시간부터 이러한 알고리즘에 대해 알아보겠습니다.