자료구조 그래프 (graph)

그래프는 입력된 자료들을 특정한 규칙을 이용해 관계를 맺어 줄 수 있는 형태의 자료구조이다.

 

예를 들면 사람들의 지인 관계는 그래프로 나타내기 좋은 형태이다.

사람 1~6 사이의 관계를 표현한 그래프의 예

 

 

그래프는 다양한 방법으로 구현할 수 있기 때문에, 어느 한 가지 구현 방식만이 그래프라고 생각하지 않는 것이 좋다.

대표적으로 사용되는 그래프 구현 방식은

 

• class, struct 등을 이용하여 정의한 노드와 포인터를 이용한 방식 (주로 c++)
• 배열을 이용한 방식 (인접 행렬, 세그먼트 트리 등등)
• 연결 리스트를 이용한 방식 (인접 리스트, map 자료구조를 이용한 방식 등등)

등이 있다.

 

 

그래프를 사용하는 방법 또한 다양한 방법이 있기 때문에, 어느 한 가지 사용법만이 그래프 자료구조를 이용했다고 생각하지 않는 것이 좋다.

대표적으로 그래프 구조를 이용해서 풀 수 있는 문제는

 

• 길 찾기 알고리즘
• 이분 매칭 알고리즘
• 위상 정렬 알고리즘
• 트리 자료구조로 확장

등등 매우 많은 형태가 있다.

 

 

 

그래프는 몇 가지 기준에 의해 분류되는 다양한 종류가 있다.

1. 그래프의 연결 방식에 따른 분류
   1. 무향 그래프 : 연결 간 방향이 정해지지 않은 그래프. 사실상 양방향 그래프와 같은 의미다.
   2. 양방향 그래프 : 연결 간 방향이 양쪽 모두 이어진 그래프. 일반적으로 지인관계에 있다고 했을때, 한쪽만 알고 다른 쪽은 모르는 경우 지인으로 생각하지 않는다. 즉 양방향으로 연결되어 있어야 지인이므로 지인관계 같은 경우 양방향 그래프로 표현이 된다,
   3. 단방향 그래프 (= 방향 그래프) : 연결 간 방향이 한쪽으로만 이어진 그래프. 대학교 수업에는 선행 이수 과목이 있는 경우가 있는데 이러한 관계는 단방향 그래프로 표현되기 좋은 예시이다.
2. 그래프의 연결에 가중치가 있는 경우에 따른 분류
   1. 가중치 그래프 : 연결 간 가중치가 존재하는 그래프, 예를 들면 도시들 간의 교통 연결망을 그래프로 나타낸다면 이동 소요시간이나, 이동 비용 등을 가중치로 두기 적절하다.
   2. 비 가중치 그래프 :  연결 간 가중치가 따로 없는 그래프, 사실상 가중치 그래프라고 표현하지 않은 일반 그래프는 비 가중치 그래프이다.

 

 

 

 

 

 

 

 

 

 

그래프는 값을 저장하는 정점 (= node)과 정점 간의 연결관계를 표현하는 간선 (= edge)으로 구성되어 있다.

또한 한 정점에서 연결된 간선 개수를 차수(= degree)라고 부른다.

 

그래프의 구성요소

 

 

 

 

추가적으로 그래프에서 파생된 자료구조로 트리 (tree) 자료구조가 있다.

트리와 그래프의 차이는 순환의 존재 유무이다.

 

순환 (= cycle) 이 존재하는 그래프와, 존재하지 않는 트리

 

그래프라고 해서 무조건 순환이 존재해야 하는 것 은 아니다, 하지만 트리는 순환이 존재하면 안 된다.

즉 트리는 그래프의 일종이다.

 

트리에 대한 내용은 트리 포스팅에서 따로 다루기로 한다.