그래프, 트리

(Graph도 일종의 자료구조이다.)

자료구조는 삽입, 삭제, 탐색이 가능하다.

그래프에서 삽입,삭제 작업은 그래프 구현을 통해, 탐색 작업은 DFS(+Backtracking),BFS를 통해 구현하다.

그래서 그래프란?

• 어떤 요소(=노드)들 사이의 연결관계(=간선)를 표현하기 위한 자료구조
• 노드와 노드를 연결하는 간선으로 이루어져 있다.
• 트리도 그래프의 일종
• 지도, 도로, 등 실생활에서의 많은 것을 그래프로 모델링 가능

그래프는 방향 그래프, 무방향(양방향) 그래프 두가지가 존재

 

연결 요소 (Connected component)

• 그래프는 모두 연결되어 있지 않을 수도 있다.

• 각각의 그룹을 연결 요소라고 부른다.

• 위는 두개의 연결 요소를 지닌 하나의 그래프

 

그래프 summary

노드와 노드를 연결하는 간선을 하나로 모아놓는 자료구조

방향그래프와 무방향그래프가 있다.

그래프는 사이클이 가능하며, 자체 간선도 가능하다.

그래프는 루트 노드, 부모-자식의 개념이 없다.

간선의 수가 제한되어 있지 않다.

트리

1. 연결 그래프이다. (연결요소가 하나이다.)
2. 방향을 무시하였을 때, 싸이클이 존재하지 않는다.
3. 트리의 간선 개수는 반드시 n-1이다.
4. 계층 관계 (부모-자식 관계)
5. 순회 방법 : DFS, BFS, 전위순회, 중위순회, 후위순회