[자료구조] 트리와 그래프의 차이

1. 그래프

---

• 노드와 노드간을 연결하는 간선으로 구성된 자료구조
• 연결되어 있는 객체 간의 관계를 표현할 수 있는 구조

 

(1) 특징

• 그래프는 네트워크 모델이다.
• 노드간에 2개 이상의 경로도 가능하다.
• 부모 - 자식 관계라는 개념이 존재하지 않는다.
• 순환 또는 비순환 구조를 이룬다.
• 방향성이 있는 그래프와 방향성이 없는 그래프가 있다. (방향그래프, 무방향 그래프 모두 존재)
• 순회 : DFS, BFS

 

 

 

---

 

 

 

 

 

2. 트리

---

• 노드와 링크로 구성된 자료 ( 연결리스트도 트리의 일종)
• 트리는 그래프의 일종이다.

 

(1) 특징

• 방향성은 존재하지만 사이클은 존재하지 않는다.  (비순환 그래프)  => Acyclic
• 부모 - 자식 관계라는 개념이 있으며 최상위에 Root 노드가 존재한다.
• 계층적 구조를 나타낼 때 사용한다. (계층 모델이다.)
• 예) 폴더구조 (디렉토리, 서브 디렉토리) , 조직도, 가계도 ....
• 순회 : DFS, BFS 방식의 전위, 중위, 후위 순회
• 두 노드 간의 경로는 1개이다.
• N개의 노드를 가진 트리는 항상 N-1 개의 간선을 가진다.