[Algorithm] Graph(그래프)

[L-j-h-c]

Graph란 무엇일까?

Graph는 일련의 노드(node, vertex, 정점) 집합 V와 엣지(edge, 간선) 집합 E로 구성된 자료구조이다. 보통 정점에는 Data가 들어가고, 간선은 그 Data들 간의 관계를 표현한다.

그래서 G = (V, E) 와 같이 표현할 수 있다.

간선으로 연결된 두 정점은 관계가 있다고 말할 수 있으며, 이를 인접(Adjacent)하다고 한다.

Graph의 종류

무향 그래프 간선에 방향이 없는 그래프로, 가장 기본적인 형태의 그래프이다.

가중 그래프 간선에 가중치가 존재하는 그래프로, 거리나 친밀도 등 수치 등 관계의 수치를 표현할 수 있다.

방향 그래프(유향 그래프) 간선에 방향이 존재하는 그래프

가중 방향 그래프 간선에 방향과 가중치가 모두 존재하는 그래프

Graph의 표현 방법

인접 행렬 n개의 정점을 가지는 그래프를 n*n 행렬 A[][]로 표현할 수 있다. 정점 i와 정점 j 사이에 간선의 존재 여부를 A[i][j]에 기록하며, 가중치를 표현할 수 있으며 간선이 존재하지 않는 경우 0 또는 무한을 이용해 표현 가능하다.

인접 행렬은 n제곱의 공간을 필요로 하는데, 두 정점 간의 인접성이 존재하는 경우보다 존재하지 않는 경우가 훨씬 많기 때문에 공간 낭비가 심하다.

인접 리스트 n개의 정점을 가지는 그래프를 n개의 연결 리스트로 표현한다. 정점 i에 연결된 정점들은 연결 리스트 i로 관리하며, 가중치가 있으면 함께 기록한다.

인접 리스트의 경우 특정 정점간의 인접성을 체크하는 과정이 비효율적이다.

인접 배열 n개의 정점을 가지는 그래프를 배열로 표현한다. 각 노드에 인접 정점 수를 명시하여, 필요한 부분까지 배열을 탐색하도록 한다.

배열을 정렬된 상태로 만들면 이진 탐색을 사용할 수 있기 때문에 |log2 K| + 1번 이내의 비교로 인접성을 확인할 수 있다.

인접 해시 테이블 n개의 정점을 가지는 그래프를 n개의 해시 테이블로 표현한다. 인접 배열에서의 2배정도 되는 크기로 해시테이블을 만든다면 인접성의 확인을 훨씬 빠르게 할 수 있다.

[L-j-h-c]

문병로 - 쉽게 배우는 자료구조