BFS와 DFS

BFS(Breadth-First Search)

너비 우선 탐색 이란 탐색을 할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘

- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법

- 최단 경로를 찾아준다는 점에서 최단 길이를 보장할 때 많이 사용한다.

-  Queue 자료구조를 사용한다.

 

알고리즘

1. 시작 노드를 큐에 삽입하면서 시작한다. 동시에 시작노드를 방문했다고 알리는 방문 처리

2. 큐에서 하나의 노드를 꺼낸다.

3. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

4. 큐가 빌 때 까지 

DFS(Depth-First Search)

깊이 우선 탐색이란 탐색을 함에 있어 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘

- 맹목적으로 각 노드를 탐색할 때 주로 사용

- Stack 자료구조를 사용한다.

 

알고리즘

1. 시작 노드를 스택에 삽입하면서 시작한다. 동시에 시작노드를 방문했다고 알리는 방문 처리

2. 스택의 TOP(최상단 노드) 확인

3. TOP(최상단 노드)과 인접한 노드 중 방문하지 않은 인접 노드가 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 TOP을 뺀다(POP).

4. 스택이 빌 때 까지 2번과 3번을 반복한다.