[Section 4] 그래프 구현 알고리즘의 종류

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

이번에는 그래프의 알고리즘을 구현하기 전에 어떤 종류의 알고리즘이 사용되는지 알아보고, 각각의 특성 비교를 통해서 어떤 알고리즘을 구현할지 결정해보자. 

1.  그래프 구현 알고리즘의 종류 _ 인접 행렬(Adjacency Matrix) 방식

그래프의 구현 알고리즘에 따라 자료 구조 상태가 달라진다. 예를 들어, 다음의 가중치가 없는 방향 그래프(Directed)를 참고로 하자. 왼쪽의 1,2,3,4로 구성된 벌텍스와 E1, E2, E3, E4, E5로 구성된 간선을 인접 행렬(Adjacency Matrix) 방식으로 구현했다고 가정하면 오른쪽 그림과 같은 행렬과 동일한 자료구조 상태를 갖게 된다. 

 

방향 그래프 예시 _ 인접 행렬 표현

 

오른쪽의 행렬을 통해서 그래프의 어떤 노드가 어디로 연결되었는지 쉽게 판단할 수 있도록 자료가 구성되었다. 이 인접 행렬 방식의 그래프 구현은 초기화 작업에서 O(n²)의 시간 복잡도와 공간 복잡도를 요구하기 때문에 그래프의 자료가 많아질수록 불리하다는 단점을 갖는다.

 

* 위에서 제시한 시간 복잡도와 공간 복잡도는 그래프의 노드 수가 간선 집안의 모든 원소 개수보다 더 많을 때 상황을 말한다. 따라서 예시로 보인 그래프의 시간 복잡도와 공간 복잡도는 O(n²) 보다 크다. 

2.  그래프 구현 알고리즘의 종류 _ 인접 리스트(Adjacency List) 방식

인접 리스트 방식은 벌텍스의 원소 v가 인접한 리스트 형태로 구현하는 방법이다. 이 방법은 간단하게 연결 리스트 알고리즘을 활용하여 구현화하는 것이 가능하다. 위에서 예로 보인 그래프가 인접 리스트 알고리즘에서 어떠한 자료 상태를 갖는지 다음의 그림을 통해 확인해보자.

 

방향 그래프 예시 _ 인접 리스트 표현

 

이 방식은 구현이 간단하며, 일반적으로 메모리 측면에서 장점을 가지고 있다는 점이 큰 장점이다. 하지만, 인접 리스트 방식은 노드의 삭제 기능을 구현하게 되면, 해당 노드의 에지에 접근하고 삭제를 구현해야 하기에 번잡하고, 삭제 기능에 대한 시간 복잡도가 큰 폭으로 증가하게 된다는 단점을 가지고 있다. 

 

* 때때로 인접 리스트와 유사한 방식으로 인접 집합(Adjacency Set) 방식으로도 그래프를 구현하기도 한다.

 

3.  그래프 구현 알고리즘 _ 정도(Degree) 특성

그래프를 구현할 때 어떤 알고리즘을 사용하는 것이 좋을까?

 

그래프의 특성 중에서 간선이 비 방향(Undirected) 이든지, 방향(Directed) 인지는 중요하지 않다. 모든 자료 구조가 동일하게 형성되기 때문이다. 그리고 이것은 가중치 그래프를 구현하고자 할 때도 마찬가지이다. 그렇다면 어떤 방식의 알고리즘이 적합한지 알기 위해서는 어떠한 특성을 비교해야 할까? 

 

가장 기본적으로 판단해야 할 사항은 그래프의 꼭짓점 노드와 간선의 개수이다. 만약 어떤 그래프의 꼭짓점 노드 개수가 간선 개수보다 더 많다면 그 그래프를 드문드문 그래프(Sparse Graph)라 하고, 반대의 경우 빽빽 그래프(Dense Graph)라고 한다.

 

빽빽 그래프는 인접 행렬 방식이 훨씬 좋고, 드문드문 그래프는 인접 리스트 방식이 구현하기에 더 적합하다.

 

* 간선의 개수와 관련된 특성을 정도(degree)이라고 한다. 즉, 정도 특성은 꼭짓점 노드들의 간선 개수를 의미한다. 비 방향 그래프에서의 정도(degree)는 인접한 간선 개수를 의미한다. 만약 그래프가 방향 그래프일 경우, 정도 특성은 들어오는 정도(indegree)와 나가는 정도(outdegree)로 구분하여 화살표의 방향을 구현한다.

 

* 그래프 구현 알고리즘의 선택에 도움이 되는 비교표는 다음과 같다.

 

알고리즘 구현 방식	초기화시 공간 측면	벌텍스와 간선의 특정 원소 탐색 측면	어떤 노드와 연결된 노드에 접근하기 위한 반복 횟수 측면
인접 행렬 방식	V2	1	V
인접 리스트 방식	E+V	노드의 정도(degree)에 의존함	노드의 정도(degree)에 의존함
인접 집합 방식	E+V	log(노드의 정도)	노드의 정도(degree)에 의존함