[알고리즘] Graph - 왜 그래프인가?

왜 그래프를 사용하는가?

문제마다 유형이 다를 것이고, 많은 영역의 문제들은 그래프(Graph)의 간결한 장점을 사용해서 분명하고 정확하게 표현될 수 있다.
예를 들어 그래프 색칠하기(Graph coloring)는 여러 곳에 활용이 될 수 있다. 지도를 표현할 때 이웃한 나라 혹은 지형에 따라 다른 색을 활용해야 하고, 학교에서 시험 시간표를 만들 때 겹치는 등의 문제를 해결할 수도 있다. 만일 어떤 학생이 동시에 진행되는 두 시험을 모두 치르려 한다면, 두 시험이 동시에 시간표로 만들어질 수 없는 것이다. 그래프에선 이 문제를 표현하기 위해서 각 시험에 대해 한 정점(Node)을 사용하고, 만일 충돌이 있을 경우엔 두 정점 사이에 간선(Edge)를 두는 것으로 해결할 수 있다. 각 시험 시간마다 자신의 색상을 갖는 것으로 함으로서 시간 배정을 하는 것은 그래프를 색칠하는 것과 같게 볼 수 있다. 이 외에도 지하철의 노선도 등 실생활에서도 여기저기에 그래프를 활용할 수 있다.

그래프의 개념

그래프는 단순하게 정점(Node)과 이 정점들을 연결하는 간선(Edge)을 모아놓은 일종의 자료구조를 말한다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있게 도와주는 도구이다.