부모와 자식으로 나눠져 있는 트리 그래프
자식은 왼쪽, 오른쪽으로 나눠진다.
전위 순회 (전위 탐색)
root -> left -> right
부모 -> 왼쪽 자식 -> 오른쪽 자식
중위 순회 (중위 탐색)
left -> root -> righi
왼쪽자식 -> 부모 -> 오른쪽 자식
후위 순회 (후위 탐색)
left -> right -> root
왼쪽자식 -> 오른쪽자식 -> 부모
깊이 우선 탐색 (DFS, Depth-First Search)
최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동
루트 노드에서 시작해서 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식
- 모든 노드를 탐색하고나 하는 경우에 이 방법을 선택함
- 깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단함
- 검색 속도 자체는 너비 우선 탐색에 비해서 느
너비 우선 탐색 (BFS, Breadth-First Search)
최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동
루트 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방식
- 주로 두 노드 사이의 최단 경로를 찾고 싶을 때 사용
ex) 'A'라는 사람의 모든 친구 관계를 그래프로 표현한 후에
'B'와 'C' 둘 사이에 존재하는 경로를 찾는 경우
- DFS는 모든 친구 관계를 다 살펴봐야 할수도 있음
- BFS는 B와 가까운 관계부터 탐
DFS와 BFS 비교
DFS(깊이 우선 탐색)
- 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색
- 스택 또는 재귀함수로 구현
BFS(너비 우선 탐색)
- 현재 정점에 연결된 가까운 점들부터 탐색
- 큐를 이용해서 구
두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간복잡도는 동일