[week8] 그래프, 트리의 차이점

그래프

그래프의 구성 요소

• 정점
• 간선

 

그래프의 방향성

방향 그래프 (Directed Graph)

 

 

무방향 그래프 (Undirected Graph, 양방향 그래프)

방향성이 없다는 것은 어느 쪽으로든 갈 수 있다는 의미이다. 

 

그래프의 순환성

그래프 내 어떤 부분이라도 순환하는 부분이 있다면 순환 그래프, 한 군데도 없다면 비순환 그래프이다. 

 

순환 그래프 (Cyclic Graph)

 

비순환 그래프 (ACyclic Graph)

 

그래프의 연결 요소 (Connected Component)

서로 완전히 분리된 요소들이 여럿 주어지는 그래프도 있다. 

각각을 연결 요소라고 한다. 

위의 그림은 두 개의 연결 요소를 가진 그래프이다. 

 

---

트리 (Tree)

 

그래프의 일종으로 순환성이 없는 무방향 그래프이다. 

트리(tree) 구조는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합하다. 

 

 

트리의 특징

• 노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가진다. [노드개수 = 간선개수 + 1]
• 임의의 두 노드 간의 가는 경로는 유일하다. [두 개의 정점(node) 사이에는 반드시 1개의 경로(edge) 만이 존재
• 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드만을 가진다.
• 순회는 Pre-order, In-order, Post-order로 이루어진다.