정의

그래프는 노드 vertex와 간선 edge을 이용한 비선형 데이터 구조이다. 보통 그래프는 데이터 간의 관계를 표현하는 데 사용한다. 데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현한다.

그래프의 특성과 종류

그래프는 방향성 가중치, 순환 특성에 따라 종류를 구분할 수 있다.

간선은 방향을 가질 수도 있고 없을 수도 있다.

방향이 있는 간선을 포함하면 방향 그래프 directed graph, 방향이 없는 간선을 포함하면 무방향 그래프 undirected graph라고 한다.

이때 방향 그래프는 어느 한쪽으로만 간선이 있는 것이 아니라 서로 반대를 가리키는 간선이 있을 수 있다.

두 번째 특성은 가중치이다. 어떤 데이터는 흐름의 방향뿐 아니라 양도 중요할 수 있다. 그런 정도를 간선에 표현할 때 이를 가중치라고 한다.

가중치가 있는 그래프를 가중치 그래프 weight graph라고 한다.

마지막 특성은 순환이다. 순환은 특정 노드에서 시작해 간선을 따라 다시 돌아오는 경로가 있는 것을 말한다.

순환이 존재하는 그래프를 순환 그래프 cycle graph라 하고, 순환이 존재하지 않는 그래프를 비순환 그래프 acyclic graph라고 한다.

그래프의 구현 방식에는 인접 행렬 adjacency matrix과 인접 리스트 adjacency list가 있다.

인접 행렬은 이중 배열을 활용하여 구현하는 경우가 많다.

이때의 배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고, 인덱스의 세로 방향을 출발 노드, 가로 방향을 도착 노드로 생각하면 자연스럽게 그래프를 표현할 수 있다.

예를 들어 아래의 그래프는


서울(0) - 400(km) -> 부산(1)

다음과 같이 표현할 수 있다.

인덱스	0	1
0	0	400
1	0	0

인접 리스트로 그래프를 표현하려면 우선 적절한 노드를 정의해야 한다. 정점(v), 가중치(w)를 묶어 관리한다.

인접 리스트 그래프 표현 방식은 다음과 같은 과정으로 동작한다.

참고자료