[CS/자료구조] 트리, 그래프 정의 및 차이점

그래프란?

노드와 노드를 연결하는 간선으로 연결된 자료 구조로, 연결되어 있는 객체 간 관계를 표현할 수 있는 비선형 자료구조이다.

특징

• 노드들 사이에 무방향/방향 경로를 가질 수 있다.
• 무방향 그래프의 경우 간선을 통해 양방향으로 갈 수 있으며 노드 A와 노드 B를 연결하는 간선은 노드의 쌍으로 표현 될 수 있다. 또한 무방향 그래프의 경우 (A, B)와 (B, A)는 같은 것으로 취급한다.
• 루트 노드라는 개념이 없으며 노드 간 계층이 존재하지 않는다.
• 사이클이 존재하며, 순환/비순환 그래프가 모두 존재한다.
• 그래프에 따라 간선이 없거나 간선의 개수는 다르다.
• 네트워크 모델이다.

관련 용어

• 차수: 노드에 연결된 간선의 수
• 인접 노드: 간선에 의해 연결되어 있는 노드. 예를 들어 상위 그림 중 노드 E의 인접 노드는 D, F이다.
• 경로: 간선을 따라갈 수 있는 길
• 경로의 길이: 경로를 구성하고 있는 간선의 수
• 단순 경로: 반복되는 간선이 없는 경로
• 사이클: 시작 정점과 종료 정점이 같은 단순경로

예시

• 지하철 노선도의 최단 경로
• 도로
• 선수과목

구현 방법

• 인접 행렬
• 인접 리스트

트리란?

그래프의 한 종류로, 그 중에서 방향성이 있는 비순환 그래프를 트리라고 한다.

특징

• 루트 노드가 존재하며 노드 간 계층이 존재한다. (계층 모델)
• 루트 노드를 시작으로 부모-자식 관계가 형성되며, 자식 노드는 반드시 한 개의 부모 노드를 갖는다. 즉, 부모-자식 간의 경로가 반드시 존재한다.
• 임의의 두 노드는 유일한 경로를 가진다.
• 사이클이 없는 연결 그래프이다.
• 노드의 수가 N개 일 때 정점의 수는 N-1개 이다.

종류

• 이진 트리: 자식 노드가 최대 2개인 트리. 종류로는 완전이진트리, 불완전이진트리, 이진 탐색트리 등이 있다.
• 이진 탐색 트리: 이진트리의 한 종류로, 부모의 키가 왼쪽 자식 노드보다 크고, 오른쪽 자식 노드보다는 작다는 특징이 있다.
• 힙 트리: 완전 트리의 일종으로 우선 순위 큐를 위해 만들어진 트리이다. 여러 값들 중 최소값, 최대값을 빨리 구하는데 사용된다.