그래프 데이터 구조 - 그래프, 무향 그래프, 유향 그래프, 가중치 그래프

그래프

그래프는 사물을 연결하는 기본 개념에서 탄생했으며 노드 사이의 연결을 보여준다

컴퓨터는 대부분 다른 컴퓨터와 연결되어 있다

컴퓨터 네트워킹이란 실제로 여러 컴퓨터를 연결하는 것이다

그래프는 컴퓨터(객체) 사이의 관계를 시각적으로 확인할 수 있는 주요 수단이다

수학에서 파생된 그래프 이론은 컴퓨터 과학의 많은 응용 분야에 적용되고 있다

그래프 vs 트리

구조화된 트리와 달리 그래프는 현실 세계에 존재하는 연결 관계를 더 잘 표현한다

현실 세계는 서로 다양하게 상호 작용을 하며, 그래프는 이러한 관계를 보다 정확하게 표현하고 모형화할 수 있다

트리는 일종의 최소화된 그래프다

그래프에서 동작하는 대부분의 알고리즘이 트리에서도 동작한다

트리는 순환이나 순환적인 상호 작용이 없는 그래프와 같다

다음은 트리 데이터 구조다

다음은 그래프 데이터 구조다

무향 그래프와 유향 그래프

그래프의 노드를 보통 객체(object) 또는 정점(vertex)이라고 한다

정점들을 연결하는 선을 에지(edge)라고 한다

에지로 연결된 정점들은 서로 인접한(adjacent) 상태다

에지는 노드 하나에서 다른 노드로 방향성을 가질 수 있다

이를 유향 그래프(directed graph)라고한다

유향 그래프는 에지에 화살표가 붙어있다

유향 그래프를 다이그래프(digraph)라고 부르기도 한다

반대로 방향성이 없는 에지를 가진 그래프를 무향 그래프(undirected graph)라고 한다

방향성을 가진 에지가 없으므로 노드 양쪽으로 에지를 타고 이동할 수 있다

그래프의 정점 하나에서 다른 정점으로 이동하려면 에지를 따라가게 되는데 이를 경로(path)라고 한다

그래프는 다수의 노드가 다수의 에지로 연결된 형태이므로 노드 사이의 관계를 볼 수 있다는 점에서 편리하다

가중치 그래프

에지는 가중치를 가질 수 있다

이는 그래프에서 에지 각각에 어떤 의미가 부여된 값이 있다는 뜻이다

에지가 가중치를 갖는 그래프를 가중치 그래프(weighted graph)라고 한다

다음은 가중치 그래프다

컴퓨터 과학의 여러 응용 분야에서 가중치 그래프를 볼 수 있으며 여러 알고리즘이 가중치 그래프에 의존한다

그래프 데이터베이스

그래프 이론이 적용된 또 다른 예는 그래프 데이터베이스 설계와 메커니즘이다

RDBMS는 표 형태의 테이블을 중심으로 데이터를 구성한다

그래프 데이터베이스는 소셜 네트워크 서비스의 친구 맺기와 같은 개념으로 데이터를 구상한다

RDBMS의 데이터 검색은 조인을 사용하는데 테이블 사이의 조인이 너무 많아질 수 있다

이는 검색 속도에 문제를 발생시킨다

그러나 그래프 데이터베이스는 데이터 사이의 관계가 복잡하지만 테이블이 아닌 데이터 중심으로 직접 연결되는 구성이므로 검색 속도가 상대적으로 빠르다