Graph

그래프

현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하는 자료 구조, 즉 정점(vertext)의 집합 V와 간선(edge)의 집합 E로 구성된 자료 구조이다. 도로망, 네트워크 망 부터 먹이 사슬, 사람들 간의 짝사랑 관계, 하루 동안의 도시 간 인구 이동 관계 등을 그래프로 표현할 수 있다.

그래프의 종류

그래프가 가지는 특징과 형태에 따라 여러 종류로 나눌 수 있다. 

• 방향 그래프 (directed graph) : 각 간선이 방향을 가지는 그래프, 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다.
• 무향 그래프 (undirected graph) : 각 간선이 방향을 가지고 있지 않은 그래프
• 가중치 그래프 (weighted graph) : 각 간선에 가중치(weight)가 부여된 그래프, 가중치는 두 도시 사이의 거리, 두 물건 사이의 교환 비율, 두 사람 사이의 호감도 등 다양한 정보를 표현하는데 사용 된다.
• 다중 그래프 (multigraph) : 두 정점 사이에 두 개 이상의 간선이 존재할 수 있는 그래프
• 단순 그래프 (simple graph) : 두 정점 사이의 최대 한 개의 간선만 존재할 수 있는 그래프
• 트리 또는 루트 없는 트리(unrooted tree) : 계층 구조(부모 자식 관계)만 없을 뿐 그래프의 형태가 트리와 같은 무향 그래프를 말한다. 즉 간선을 통해 두 정점을 잇는 방법이 딱 하나 밖에 없다.
• 이분 그래프 (bipartite graph) : 그래프의 정점들을 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만들 수 있는 그래프
• DAG (directed acyclic graph) : 사이클 없는 방향 그래프, 보통 여러 작업들 간의 상호 의존 관계를 표현할 때 DAG로 표현한다.

그래프 종류

그래프의 경로

그래프에서 경로(path)란 정점 V₁에서 시작하여 정점 V₂로 가는 경로를 뜻하며 두 정점 사이를 잇는 간선 또는 정점을 순서대로 나열해 경로를 표현한다.

예를 들어 위의 그래프에서 간선으로 표현한 경로 (2,3), (3,1), (1,2) 또는 단순하게 정점의 번호만을 써서 표현한 경로 2,3,1은 정점 2에서 시작해서 정점 1로 가는 경로를 뜻한다.

 

위의 그래프에는 2, 3, 1 뿐만 아니라 2, 3, 1, 2, 4 또는 2, 4 ,5 또는 2, 4, 5, 2, 3 등등 많은 경로가 존재한다. 경로 중에서 한 정점을 한 번만 지나는 경로를 단순 경로(simple path)라 한다. 경로 2, 3, 1, 2, 4는 정점 2를 두 번 지나기에 단순 경로가 아니다. 현대 그래프 이론에서 경로라 하면 보통 단순 경로를 의미하며 한 정점을 두 번 이상 지나갈 수 있는 경로를 얘기할 때는 이 사실을 명시한다. 단순 경로는 다른 말로 사이클을 형성하지 않은 경로를 말한다.

 

경로 중에 2, 3, 1, 2 또는 2, 4, 5, 2와 같이 시작점과 끝점이 같은 경로를 사이클(cycle)이라 부른다.

그래프 표현 방법

그래프는 트리와 달리 정적인 용도로 사용되기에(정점과 간선의 추가 삭제가 자주 일어나지 않음) 일반적으로 그래프의 구조 변경이 어렵더라도 간단하고 메모리를 적게 차지하는 방법으로 구현한다.

• 인접 리스트 (adjacency list) : 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장한다. 따라서 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현한다.
• 인접 행렬 (adjacency matrix) : 그래프의 정점의 개수 V X V 크기의 행렬을 만들어 구현한다. 인접 행렬 [i, j]는 정점 i에서 정점 j로 가는 간선이 있는지를 나타낸다.

인접 행렬의 장점으로 간선 (u, v)가 존재하는지를 단 한번에 알 수 있지만 간선의 개수와 상관 없이 V X V 크기의 2차원 배열을 사용하기 때문에 간선의 개수와 상관 없이 O(V²) 공간이 사용된다는 단점이 있다. 인접 리스트의 장점으로 O(V + E) 만큼의 공간을 사용하지만 간선 (u, v)가 존재하는지 파악하려면 정점 u의 리스트를 순차 탐색해야 한다는 단점이 있다.

그래프 표현 방법