그래프(Graph)

 

그래프의 탐색(Search)

: 그래프의 정점들을 방문하여 목표 정점을 찾는 것

 

종류

• 깊이 우선 탐색(DFS)
• 너비 우선 탐색(BFS)

---

깊이 우선 탐색 ( DFS  : Depth First Search )

정의

: 자식, 그 자식의 자식 등으로 계속 이동하며 깊은 노드부터 처리하는 방식

: 자식노드 방문 --> 형제노드 방문 (자식 노드 우선!)

 

EX)

A의 이웃노드 : B,D,E

---

너비 우선 탐색 ( BFS : Breath First Search )

정의

: 자신과 가까운 형제 노드부터 처리하는 방식

: 형제 노드 방문 --> 자식 노드 방문 (형제 노드 우선!)

 

EX)

A의 이웃노드 : B,D,E

---

트리 구조(Tree)

: 그래프의 특수한 한 형태

: 노드들이 나무 가지처럼 연결된 비선형적(non-linear), 계층적 자료구조

: 1개의 루트 노드(Root Node)를 가지며, 회로가 없어야 한다.

 

---

이진 트리 (Binary Tree)

: 내부의 모든 노드들이 2개 이하의 자식 노드(자식이 없을 수도 있음)를 가지는 트리 구조

: 루트 노드(Root Node)를 기준으로 왼쪽 자식 노드와 오른쪽 자식 노드 집합으로 이루어짐

 

 

이진 트리의 순회 방식

• 전위 순회 (Preorder Traversal) : Root -> L 자식 -> R 자식
• 중위 순회 (Inorder Traversal) : L 자식 -> Root -> R 자식
• 후위 순회 (Postorder Traversal) : L 자식-> R 자식 -> Root
• 층별 순회 (Level-Order Traversal) : 노드의 순서대로

 

참고 사이트

https://withhamit.tistory.com/282

트리 순회(전위 순회, 중위 순회, 후위 순회)