DFS와 BFS

목차

1. DFS란?
2. BFS란?
3. 그래프에서 적용된 모습
4. 차이점 비교

1. DFS란?

DFS는 Depth-First Search의 약자로 깊이 우선 탐색이란 뜻입니다.
트리에서 사용한다면 다음과 같은 순서를 가집니다.

선택 가능한 자식 노드가 없을 때까지 자식 노드를 우선적으로 선택합니다.
모든 노드를 탐색해야 할 때 주로 사용됩니다.

2. BFS란?

BFS는 Breath-First Search의 약자로 넓이 우선 탐색이라는 뜻입니다.
트리에서는 다음과 같은 순서를 가집니다.

노드를 탐색하는 데 있어 자식 노드와 같은 레벨의 노드 중 같은 레벨의 노드를 우선적으로 탐색하는 알고리즘입니다.
특정 조건을 만족하는 노드의 최단 거리를 구해야 할 때 사용됩니다.

3. 그래프에 적용된 모습

자식 노드 대신 인접한 정점으로 해당 알고리즘을 실행시켜 주면 됩니다.
인접한 정점 전부를 확인할 것인지, 아니면 하나만을 먼저 확인하고 다음 정점으로 넘어갈지를 생각해 주시면 됩니다.

4. 차이점 비교