<TIL 20.06.22> DFS && BFS

DFS (깊이 우선탐색)

DFS는 Depth-First Search의 약자로, 트리구조에서 루트부터 시작해 한 루트로 탐색하다가 최대한 깊숙히 들어가며 탐색 후 다시 돌아가 다음 루트를 탐색하는 방법이다. 일반적으로 재귀호출을 사용하거나 스택배열로 구현한다.

 

 

Backtracking (백트래킹)

 

백트래킹이란 모든 경우의 수를 전부 고려하는 알고리즘이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다고 한다. 구조적으로 깊이우선탐색을 기반으로 한다. 어떤 노드의 유망성을 점검하고 유망하지 않으면 그 노드의 부모 노드로 돌아간 후 다른 자손의 노드를 검색하는 것을 말한다. 즉, 스택에 자식노드를 넣기 전에 유망한지를 확인하고 스택에 넣는다.

 

 

 

BFS (너비 우선 탐색)

BFS는 Breadth-First Search의 약자로, 너비 우선 탐색도 루트부터 시작해 인접한 모든 정점들을 우선 탐색하는 방법이다. 더 이상 탐색하지 않은 정점이 없을때까지 탐색하기에 모든 정점들에서 대해서 너비우선탐색을 적용한다. 일반적으로 큐배열로 구현한다.

 

 

 

 

 

 

이미지 출처 : https://developer-mac.tistory.com/64