[알고리즘]Tree, Graph

1. 트리(Tree)

루트(Root)라는 하나의 꼭짓점을 시작으로 간선(edge)으로 연결한다.
각 데이터는 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.

트리구조의 특징

• 깊이(Depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이
• 레벨(Level) : 같은 깊이를 가지고 있는 노드, 같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고도 한다.
• 높이(Height) : 리프 노드를 기준으로 루트까지의 높이
• 서브트리(Sub tree) :트리 구조를 갖춘 작은 트리

---

2. 그래프(Graph)

여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조

 

그래프의 구조

• 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.
• 간접적인 관계면 몇 개의 선에 걸쳐 이어진다.
• 하나의 점을 그래프에서는 정점(Vertex)라고 표현하고, 하나의 선은 간선(edge)라고 한다.

그래프 용어 정리

• 정점 (vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소
• 간선 (edge): 정점 간의 관계 (정점을 이어주는 선)
• 인접 정점 (adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점
• 가중치 그래프 (weighted Graph): 연결의 강도(추가적인 정보, 위의 예시에서는 서울-부산으로 가는 거리 등)가 얼마나 되는지 적혀 있는 그래프
• 비 가중치 그래프 (unweighted Graph): 연결의 강도가 적혀 있지 않는 그래프
• 무(방)향 그래프 (undirected graph): 앞서 보았던 내비게이션 예제는 무(방)향 그래프. 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는 것도 가능. 하지만 단방향(directed) 그래프로 구현된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현가능 
• 진입 차수 (in-degree) / 진출 차수 (out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 표시
• 인접 (adjacency): 두 정점 간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점
• 자기 루프 (self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현. 다른 정점을 거치지 않는다는 것이 특징
• 사이클 (cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현. 내비게이션 그래프는 서울 —> 대전 —> 부산 —> 서울로 이동이 가능하므로, 사이클이 존재하는 그래프