BFS

알고리듬 - 깊이 우선 탐색, 너비 우선 탐색

깊이 우선 탐색(DFS: Depth-First Search)과 너비 우선 탐색(BFS:Breadth-First Search)은 그래프 완전 탐색 기법 중 하나이다. 이 둘에 대해 알아보자. 깊이 우선 탐색(DFS) DFS는 그래프의 시작 노드에서 출발해 한쪽 분기를 최대 깊이까지 탐색한 후 다른 쪽 분기를 탐색하는 형식이다. 방문한 정점을 시작 정점으로 하여 다시 탐색을 진행하는 방식으로 진행한다. DFS는 노드 수를 V, 간선 수를 E라고 했을 때 그래프가 인접 리스트로 구현되었으면 시간복잡도가 O(V + E), 그래프가 인접 행렬으로 구현되었으면 시간복잡도가 O(n2)이다. 동작 그림으로 보자. 아래와 같은 그래프가 있고 정점 0을 시작 정점으로 하였다. 정점 1을 먼저 탐색한다고 했을 때, 다시 정..