자료구조 - 그래프

그래프는 점과 선으로 이뤄진 자료구조다 보통은 순환이 가능하면 그래프라고 판단한다.

 

먼저의 그래프의 구성을 살펴보자면 그래프의 점은 '정점' 다른 말로 노드라고도 부르며 선은 '간선' 이라고 부른다. 순환은 특정 노드에서 출발해 다시 돌아올 수 있는 것을 뜻하며 순환되지 않아도 그래프인 경우도 존재한다. 아래 그림을 보자.

 

 

위와 같이 1 에서 출발해 1 로 가지 못하는 경우에는 비순환 그래프 이며 동시에 우측의 트리로 표현이 가능하다. 만약 저 상태에서 그림과 같이 간선이 추가 되면 순환이 가능한 상태가 되며 트리가 아닌 그래프가 된다. 또한 위와 같이 화살표가 없이 단순 선형태의 간선은 양방향 간선으로 판단하며 두 노드가 서로 접근이 가능하다. 마지막으로 간선에 숫자를 추가해 가중치를 넣을 수 도 있는데 일반적으로는 해당 간선을 사용하여 이동 시 소비되는 비용(거리나 시간)을 의미한다. 

 

 

그럼 이어서 그래프의 구현을 살펴보자.

그래프는 크게 행렬과 리스트로 표현이 가능하다.

 

 

주어진 그래프를 행렬로 표현하면 위처럼 행렬에 서로 접근 가능할 경우 1 로 접근이 불가능 할 경우 0 으로 표현한다. 또한 자기자신을 접근하는 경우에 대해서는 일반적으로 0 으로 표기하지만 상황에 따라 1 로 바꿀 수 있다. 그리고 살펴보면 순수 양방향 그래프의 행렬은 자기자신 접근 원소들 (0, 0) -> (n-1, n-1) 대각선을 기준으로 대칭이기에 대칭의 절반만 순회해도 그래프의 전체 정보를 알 수 있기도 하다. 

 

 

하지만 간선의 가중치나 방향이 들어가게 되면 대부분의 경우에는 노드 사이에 단일 경로가 아닌 다중 경로로 주어지는데, 그렇게 될 경우 행렬로는 해당 그래프의 정보를 표현할 수 없다. 그렇기에 필자는 주로 다음과 같이 리스트 형식으로 구현한다. 

 

 

리스트 그래프 구현은 노드 간 접근 가능 여부를 바로 알 수 있는 행렬 구현에 비하면 속도는 느리지만 보다 유연하게 그래프의 정보를 표현할 수 있다. 그래서 필자의 경우에는 리스트에 해쉬 테이블을 섞어서 색인 속도도 높이며 동시에 다른 정보도 같이 매핑하여 문제를 해결하는 경우가 많다. 

 

결국 다른 비선형 자료 구조인 트리 또한 어떻게 보면 그래프의 확장 영역이라고 볼 수 있으며 그래프는 비선형 자료구조의 기본이라고 생각된다. 그만큼 문제도 상당히 까다로운 경우가 많다;