자료구조 기초 - 그래프

그래프

그래프는 노드 사이의 연결을 보여준다. 컴퓨터 네트워킹이랑 여러 컴퓨터를 연결하는 것이다. 그래프는 컴퓨터(객체) 사이의 관계를 시각적으로 확인할 수 있는 주요 수단이다. 수학에서 파생된 그래프 이론은 컴퓨터 과학의 많은 응용 분야에 적용되고 있다.

그래프는 기본적으로 다수의 원이 다수의 선으로 연결된 형태이므로 객체 사이의 관계를 볼 수 있다는 점에서 편리하다.

많은 탐색 기반 알고리즘이 그래프에 의존한다. SNS를 설계할때도 그래프를 변형하여 사용한다.

그래프 데이터베이스는 테이블로 연결되는 것이 아닌 데이터 중심으로 직접 연결되는 구성이므로 관계형 데이터베이스 관리 시스템(RDBMS)의 문제점을 개선하기 위해 사용될 수 있다.

 

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

일부 프로그래머는 트리를 일종의 최소화된 그래프로 여긴다. 그래프에서 동작하는 대부분의 알고리즘이 트리에서도 동작하고, 트리는 기본적으로 순환이나 순환적인 상호 작용이 없는 그래프와 같기 때문이다.

 

그래프의 노드를 보통 객체(Object) 또는 정점(Vertex)이라고 하며, 정점들을 연결하는 선을 엣지(Edge)라고 한다.

엣지로 연결된 정점들은 서로 인접한 상태(Adja-cent)다.

 

그래프의 정점 하나에서 엣지를 따라 다른 정점으로 이동하는 것을 경로(Path)라고 한다. 엣지가 정점 하나에서 시작하여 다시 해당 정점으로 이어지는 형태는 루프(Loop)라고 한다.

어떤 그래프가 더 큰 그래프의 일부라면 해당 그래프를 하위 그래프 또는 서브 그래프라고 한다.

 

무향 그래프와 유향 그래프

엣지는 노드 하나에서 다른 노드로 방향성을 가질 수 있다. 이러한 엣지를 가진 그래프를 유향 그래프(Directed Graph)라고 한다. 유향 그래프에는 엣지에 화살표가 붙어있으며, 정점을 연결하는 엣지는 각각 하나의 방향을 갖는다. 이러한 엣지를 유향 엣지(Directed Edge)또는 화살표(Arrow)라고 한다. 유향 그래프는 다이그래프(Digraph)라고 부르기도 한다.

반대로 방향성이 없는 엣지를 가진 그래프를 무향 그래프(Undirected Graph)라고 한다. 방향성을 가진 엣지가 없으므로 노드 양쪽으로 엣지를 타고 이동할 수 있다.

 

가중치 그래프

엣지 각각에 가중치(어떤 의미가 부여된 값)을 가진 그래프.

무향 가중치 그래프와 유향 가중치 그래프도 있다.