[자료 구조/알고리즘] 그래프와 트리

그래프(graph)란 노드(node)와 간선(edge)의 집합으로 구성되는 추상 자료형(ADT, abstract data type)이다. 간선은 서로 다른 두 노드를 연결하는 선을 의미하며 방향성(direction)과 가중치(weight)를 가질 수 있다. 간선은 두 노드의 연결 관계를 나타내며, 간선의 가중치는 간선에 부여하는 데이터로서 노드 간 거리, 이동 비용 등을 의미한다. 두 노드 간 존재하는, 하나 이상의 간선 집합을 경로(path)라고 한다.

그래프는 간선의 방향(노드 간 방향)의 존재 여부와 방향의 종류에 따라 다음과 같이 구분된다.

• 방향 존재 여부에 따른 구분
  • 방향 그래프 (directed graph): 간선에 방향이 존재한다. 간선은 하나 또는 두 개의 가중치를 가질 수 있다.
  • 무향 그래프 (undirected graph): 간선에 방향이 존재하지 않는다. 간선은 하나의 가중치를 가질 수 있다.
• 방향 그래프의 경우 방향의 종류에 따른 구분
  • 단방향 (unidirectional graph): 간선이 방향이 한쪽을 향한다. 간선은 하나의 가중치를 갖는다. 간선이 노드 A에서 노드 B 방향을 가르키지만, 노드 B에서 노드 A 방향을 가르키지 않는 경우 간선은 단방향이다.
  • 양방향 (unidirectional graph): 간선의 방향이 양쪽을 향한다. 간선은 두 개의 가중치를 갖는다. 간선이 노드 A에서 노드 B 방향을 가르키면서, 노드 B에서 노드 A 방향을 가르키는 경우 간선은 양방향이다.

트리(tree)는 부모(parent)와 자식(child) 관계로 구성되는 계층적인 구조를 갖는 그래프 자료 구조이다. 그래프 자료 구조의 하위 개념으로 다음과 같은 특성을 갖는다.

• 비순환 (acyclic): 트리는 순환 구조를 갖지 않는다. 노드 A가 B와, 노드 B가 C와 연결되고 노드 C가 다시 노드 A와 연결되는 순환 구조가 존재하는 경우 트리가 아니다.
• 무방향 그래프 (undirected graph): 트리에서 모든 간선에는 방향이 존재하지 않는다. 간선은 하나의 가중치를 가질 수 있다.
• 부모/노드 관계: 노드의 부모 노드는 단 하나여야 한다. 노드의 부모 노드가 2개 이상인 경우 트리가 아니다.
• 단일 경로 (single path): 트리에서 임의의 두 노드 간에는 단 하나의 경로만 존재한다. 한 노드에서 다른 노드로 가는 방법은 오직 하나 뿐이다.