[알고리즘] 트리 탐색, 그래프 탐색

트리 탐색 알고리즘과 그래프 탐색 알고리즘은 

둘 다 특정한 구조를 갖는 자료구조를 탐색하는 알고리즘

하지만 트리와 그래프는 서로 다른 특징과 제약 조건을 가지고 있어서 각각에 맞는 탐색 알고리즘이 존재

 

이진트리(Binary tree)

이진트리는 모든 노드가 2개의 서브 트리를 갖는 트리

이때 서브 트리는 공집합일 수도 있다

 

 

 

트리 탐색 알고리즘

전위 순회

루트 노드를 먼저 방문한 후, 왼쪽 서브트리를 전위 순회하고 오른쪽 서브트리를 전위 순회하는 방식

노드를 방문하는 순서는 "루트 노드 - 왼쪽 서브트리 - 오른쪽 서브트리"

 

 

 

 

중위 순회

왼쪽 서브트리를 중위 순회한 후에 현재 노드를 방문하고, 오른쪽 서브트리를 중위 순회하는 방식

노드를 방문하는 순서는 "왼쪽 서브트리 - 루트 노드 - 오른쪽 서브트리"

 

 

후위 순회

왼쪽 서브트리를 후위 순회한 후에 오른쪽 서브트리를 후위 순회하고, 마지막으로 현재 노드를 방문하는 방식

노드를 방문하는 순서는 "왼쪽 서브트리 - 오른쪽 서브트리 - 루트 노드"

 

 

 

 

그래프 탐색 알고리즘

 

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

한 노드에서 출발하여 인접한 노드를 방문하고,

그 인접한 노드의 인접한 노드를 방문하는 식으로 탐색하는 방법

스택(Stack)이나 재귀 함수를 이용하여 구현

 

 

 

 

너비 우선 탐색(Breadth-First-Search, BFS)

그래프나 트리를 탐색하는 방법 중 하나로, 

루트(혹은 시작점)에서 시작하여 인접한 모든 노드를 먼저 방문한 후, 

더 이상 방문하지 않은 노드 중 하나를 선택하여 

해당 노드의 인접한 노드를 방문하는 방식

즉, 같은 레벨에 있는 노드들을 먼저 방문하는 방법