그래프

그래프

그래프는 사물을 연결하는 기본 개념에서 탄생했으며 노드 사이의 연결을 보여준다. 또한 그래프는 컴퓨터(객체) 사이의 관계(네트워킹)를 시각적으로 확인할 수 있는 주요 수단이다. 한편 그래프는 컴퓨터 과학과 수학의 관계를 확인할 수 있는 중간 영역 개념이기도 하다. 수학에서 파생된 그래프 이론은 컴퓨터 과학의 많은 응용 분야에 적용되고 있다.

그래프 vs 트리

그래프는 루트 노드가 없는 트리처럼 보이며, 부모 노드 또는 자식 노드로 식별할 수 있는 노드를 찾을 수 없다. 매우 구조화된 트리와 달리 그래프는 현실 세계에 존재하는 다양하게 상호 작용하는 연결 관계를 더 잘 표현한다. 트리는 일종의 최소화된 그래프(순환이나 순환적인 상호 작용을 제외한 그래프)로 여겨지기도 하는데, 그래프에서 동작하는 대부분의 알고리즘이 트리에서도 동작하기때문이다.

무향 그래프와 유향 그래프

그래프의 노드를 보통 객체 object 또는 정점 vertex이라고 하며, 정점들을 연결하는 선을 에지 edge라고 한다. 에지로 연결된 정점들은 서로 인접한 adjacent상태다.

에지는 노드 하나에서 다른 노드로 방향성을 가질 수 있다. 이러한 에지를 가진 그래프를 유향 그래프 directed graph 또는 다이그래프 digraph라고 한다.

반대로 방향성이 없는 에지를 가진 그래프를 무향 그래프 undirected graph라고 한다. 무향 그래프에서는 노드 양쪽으로 에지를 타고 이동할 수 있다.

그래프의 정점 하나에서 다른 정점으로 이동하면 에지를 따라가게 되는데 이를 경로 path라고 한다. 그리고 에지가 정점 하나에서 시작하여 다시 해당 정점으로 이어지는 형태를 루프 loop라고 한다.

그래프는 객체(노드) 사이의 관계를 볼 수 있다는 점에서 편리하다. 이러한 그래프의 속성은 많은 탐색 기반 알고리즘에서 사용된다.

가중치 그래프

에지는 가중치를 가질 수 있다. 이는 그래프에서 에지 각각에 어떤 의미가 부여된 값이 있다는 뜻이다. 이렇게 에지가 가중치를 갖는 그래프를 가중치 그래프 weighted graph 라고 한다.

그래프와 소셜 네트워크 서비스

sns 프로그램을 설계할 때는 그래프를 사용한다. 사람 1명의 프로필은 그래프에서 노드 하나라고 생각할 수 있다.

그래프 데이터베이스

데이터를 저장할 경우 파일 시스템을 사용할지 데이터베이스 관리 시스템을 사용할지 선택할 수 잇다. 파일 시스템에 데이터를 저장할 경우 다음과 같은 단점이 있다.

• 연산 실행이 제한적이다.
• 데이터 형식이 제각각이다.
• 데이터 중복이 발생한다.
• 보안이 허술하다.

이러한 파일 시스템의 단점을 해결하기 위해 관계형 데이터베이스 관리 시스템 relational database management system, RDBMS이 등장했다. RDBMS는 행과 열로 구성된 테이블에 데이터를 저장하여 파일 시스템의 결함을 개선한다. 또한 RDBMS가 유용한 이유 중하나는 키 시스템이다. 데이터베이스의 키는 조건을 만족하는 데이터를 찾거나 정렬할 때 기준이 되는 속성을 담은 것이다. 데이터를 식별하는 속성이 담겨 Null 값이면 안 되는 기본 키와, 다른 테이블과의 관계를 참조하는 속성 정보를 담은 외래 키가 있다.

RDBMS는 데이터베이스가 확장될 때 문제가 발생한다. 연결된 테이블 사이의 일부 연산은 컴퓨터의 많은 자원을 필요로 한다. 이때 그래프 데이터 구조로 설계된 그래프 데이터베이스를 통해 문제점들을 개선할 수 있다.

RDBMS의 데이터 검색은 여러 데이터베이스를 연결해서 검색하는 조인을 사용하는데 테이블 사이의 조인이 너무 많으면 테이블을 거쳐 데이터에 접근하는 과정이 반복되므로 데이터베이스를 검색하는 속도에 문제가 발생한다. 그러나 그래프 데이터베이스는 테이블이 아닌 데이터 중심으로 직접 연결되는 구성이므로 데이터베이스의 검색 속도가 상대적으로 빠르다.