깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)

DFS(Depth First Search)는 루트 노드에서 시작해 자식 노드들을 순서대로 탐색하는 알고리즘으로 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

 

 

길찾기 같은 기능을 구현하거나 모든 노드를 방문해야하는 경우에 사용한다. 재귀함수는 스택으로 구현한다.

 

 

BFS(Breadth First Search)는 루트노드에서 시작해 인접한 노드들을 먼저 탐색하는 알고리즘으로 DFS와는 반대다. 

 

 

최단경로를 구현할때 사용한다. 큐로 구현한다.

 

이제 그래프를 만들어서 구현을 해보겠다.

 

vector를 사용해서 위의 그래프를 만들었다.

 

DFS

재귀함수를 사용하여 구현했다. bool형 배열로 방문했는지 체크하고 인접 노드들이 방문했는지 체크하여 방문하지 않았다면 재귀적으로 그래프를 탐색한다.

결과값

 

BFS

BFS는 큐를 사용하여 구현했다. 방문한 노드들을 큐에 추가여 방문체크하고 다시 삭제하고 인접 노드들이 방문했는지 체크하여 방문하지 않았으면 큐에 추가하면서 그래프를 탐색한다.

결과값

 

 

결과값을 비교해보면 확실히 탐색하는 과정이 다르다는 것을 볼 수 있다.