[DFS&BFS] 개념 정리 및 구현

01. 그래프 탐색 알고리즘

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘으로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다.

 

 

 

02. 그래프의 구현 방법

인접 리스트 표현

각 정점과 인점한 정점들을 저장해서 그래프를 표현하는 방법으로,

예를 들어 그래프의 저장 공간을 이차원 벡터로 표현한다면, 다음과 같게 됩니다.

vector<vector<int>> adjacent;

adjacent[i

 

 

03. 깊이 우선 탐색(DFS)

깊이 우선 탐색은 한 정점으로부터 가장 깊은 노드까지 탐색하고, 더 이상 갈 곳이 없어지면 원점으로 돌아와 다른 노드를 탐색하는 방법으로, 다음 그림과 같이 탐색을 진행합니다.

 

 

   탐색 순서: 0 -> 1 -> 3 -> (4 -> 1 -> 0) -> 2 -> 5 -> (6 -> 2 -> 0)

 

   괄호한 부분은 갈 곳이 없어져 이전으로 돌아가는 과정이며,

   0의 인점한 정점은 1, 2 두개로,

   (2 -> 0) 이후엔 갈 곳이 없어 탐색을 종료하게 됩니다.

 

 

 

 

 

 

04. 깊이 우선 탐색(DFS) 구현