그래프(Graph) 자료구조

그래프(Graph)는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하는 자료구조이다. 여러 도시들을 연결하는 도로망, 사람들 간의 관계, 웹 사이트 간의 링크 관계 등이 그러한 연결 구조이다. 그래프는 계층 구조인 트리와는 다르게 부모 자식 관계에 관한 제약이 없다. 그러므로 훨씬 다양한 구조를 표현할 수 있다.

그래프의 정의

그래프 G(V,E) 는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V 와 이들을 연결하는 간선(edge)들의 집합 E 로 구성된 자료구조이다. 다시 말해, 그래프는 기본적으로 정점들과 간선들로 정의된다. 여기에서 정점이나 간선에 추가적인 속성을 부여할 수도 있고, 제약을 두기도 한다.

DP와 브루트 포스는 어떤 하나의 방법에 가깝다. DP는 어떠한 문제를 점화식을 세워서 푼다. 브루트 포스는 모든 경우의 수를 살펴보아야 하기 때문에, 어떠한 방법으로 모든 경우를 살펴볼지를 결정한 후에 푼다. 이와 달리, 그래프는 문제의 상황을 그래프로 모델링 한 다음에 여러가지 알고리즘을 수행하게 된다. 알고리즘은 변하지 않고 어떻게 문제상황을 그래프로 만들지가 관건이다.

그래프의 종류

그래프는 표현하고자 하는 대상에 따라 여러 가지 변형된 형태를 가질 수 있다. 대표적으로 방향 그래프(directed graph)가 있는데, 이 그래프에서는 각 간선이 방향이라는 새로운 속성을 갖는다. 반대로, 간선에 방향이 없는 양방향 그래프(undirected graph)도 있다. 실제로 구현할 때는 양방향 그래프도 방향 그래프로 표현하는 것이 편리하며, 양방향을 모두 표현하면 된다.

가중치 그래프(weighted graph)는 간선에 가중치를 부여하여 간선마다 속성을 달리할 수 있다. 이 속성은 이동하는 거리, 이동하는데 필요한 시간, 이동하는데 필요한 비용 등이 있을 수 있다.

그래프의 경로

그래프의 경로란, 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것이다. 경로나 사이클에서 같은 정점을 두번이상 방문하지 않는 경로를 단순 경로라고 한다.

가중치
간선에 가중치가 있는 경우에는 A에서 B로 이동하는 거리, 이동하는데 필요한 시간, 이동하는데 필요한 비용 등이 있다. 가중치가 없는 경우에는 가중치가 1이라고 생각하면 된다.

그래프의 표현

그래프는 정정과 간선으로 표현되는데, 정점을 모두 저장한다면 경우의 수가 엄청 많이 생긴다. 반면에 간선의 연결정보를 모두 저장한다면 그래프를 정확히 그릴 수가 있게된다. 따라서 그래프를 저장한다는 것은 정점의 수와 간선의 연결정보를 저장하는 것이다.

이 두 가지 정보를 저장하는 방법은 크게 두 가지가 있다. 첫번째는 인접 행렬 표현방식이고, 두번째는 인접 리스트 표현 방식이다. 효율의 관점에서 이 두 가지 저장방식은 차이가 있다.

인접 행렬

정점의 개수를 V라고 했을때, VxV 이차원 배열을 이용한다. A[i][j]는 정점 i에서 정점 j로 가는 간선의 존재 유무를 나타낸다.

인접 리스트

리스트를 이용해서 구현한다. 링크드 리스트처럼 길이를 동적으로 변결할 수 있는 배열을 사용한다. C++에서는 Vector, JAVA에서는 ArrayList, Python은 배열을 사용하면 된다.

공간 복잡도

• 인접 행렬 : O(V^2)
• 인접 리스트 : O(E)

한 정점과 연결된 모든 정점을 찾기위해서 인접 행렬은 정점 개수의 제곱만큼을 모두 탐색해야 한다. 반면에 인접 리스트는 이미 연결된 것만을 저장했으므로, 간선의 개수만큼만 보면 된다.

인접 행렬은 (u,v)간선이 있는지 없는지를 O(1) 또는 O(차수)만에 찾을 수 있다. 하지만 그래프 문제에서 가장 중요한 것은 한 정점과 연결된 모든 간선을 찾는 것이므로, 공간도 작게 사용하고 탐색 시간도 빠른 인접 리스트가 훨씬 더 많이 사용된다.